设计一个算法,将带头的单链表逆置
时间: 2024-09-30 13:13:27 浏览: 10
设计一个算法来逆置带头的单链表,可以采用迭代或递归的方式。这里我们提供一种迭代的方法,它更直观且空间复杂度较低。
**迭代法(非递归):**
1. 定义两个指针,`prev` 和 `curr`,初始都指向头节点 `head`。
2. 创建一个临时变量 `nextNode`,用于保存当前节点的下一个节点。
3. 进入循环,当 `curr` 不为空时,执行以下步骤:
- 将 `curr` 的下一个节点赋值给 `nextNode`。
- 更新 `curr` 指向 `prev`。
- 更新 `prev` 指向 `curr`(即原 `curr.next`)。
4. 循环结束后,`prev` 就是指向了新的头节点,因为原来的头节点现在变成了最后一个节点。所以返回 `prev` 作为新链表的头。
下面是伪代码形式:
```plaintext
def reverseList(head):
prev = None
curr = head
while curr is not None:
nextNode = curr.next
curr.next = prev
prev = curr
curr = nextNode
return prev
```
相关问题
用c语言设计一个算法,将带头的单链表逆置
在 C 语言中,我们可以使用迭代的方式来设计一个简单算法来逆置带头结点的单链表。这里是一个基本的步骤:
1. 定义两个指针,`prev` 和 `current`,初始时都指向头节点。
2. 当 `current` 指针不为空时,进行循环操作:
- 将 `current` 的下一个节点赋值给 `temp`(临时存储当前节点的下一个节点)
- 更新 `current` 的下一个节点为 `prev`
- 移动 `prev` 和 `current` 向前,即 `prev = current`, `current = temp`
3. 循环结束后,`prev` 就指向了新的头节点。
下面是对应的伪代码和 C 语言代码实现:
```c
// 结构体定义链表节点
typedef struct Node {
int data;
struct Node* next;
} Node;
// 函数定义逆置链表
Node* reverseList(Node* head) {
Node* prev = NULL; // 初始化prev为NULL
Node* current = head; // 初始化current为头节点
while (current != NULL) { // 当current非空时
Node* temp = current->next; // 保存当前节点的下一个
current->next = prev; // 更新当前节点的next为prev
prev = current; // 移动prev
current = temp; // 移动current
}
return prev; // 返回新头节点
}
```
设计一个算法,将带头节点的单链表逆置
可以使用三个指针依次遍历链表,将每个节点的 next 指针指向它的前驱节点,即可实现链表的逆置。
具体的实现方式如下:
```python
def reverse_linked_list(head):
if head is None or head.next is None:
return head
prev = None
curr = head.next
while curr is not None:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
head.next = prev
return head
```
其中,head 表示链表的头节点,prev 表示当前节点的前驱节点,curr 表示当前节点,next_node 表示当前节点的后继节点。
该算法的时间复杂度为 O(n),其中 n 表示链表的长度。