用双指针实现反转链表
时间: 2024-10-24 14:18:46 浏览: 7
用双指针(也叫快慢指针)实现链表反转是一个高效的迭代方法。以下是使用Python的一种常见做法:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list_iterative(head):
prev = None
curr = head
while curr is not None:
# 使用临时变量temp保存下一个节点
temp = curr.next
# 翻转当前节点的next指向上一个节点
curr.next = prev
# 指针向后移动
prev = curr
curr = temp
return prev # 新链表的头节点就是原链表的尾节点
```
代码解释:
1. 初始化两个指针`prev`和`curr`,初始时`prev`为`None`,`curr`指向链表头。
2. 在循环中,首先保存`curr`的下一个节点到`temp`。
3. 将`curr`的`next`指针指向前一个节点`prev`,完成了当前节点的反转。
4. 指针`prev`和`curr`分别向后移动一位,直到`curr`变为`None`(表示已经遍历到链表尾部)。
5. 最后返回`prev`,它现在指向的就是反转后的链表的新头。
相关问题
用C语言实现双链表反转
以下是C语言实现双链表反转的代码:
```
#include <stdio.h>
#include <stdlib.h>
// 双链表节点结构体
typedef struct ListNode {
int val;
struct ListNode* next;
struct ListNode* prev;
} ListNode;
// 反转双链表函数
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
curr->prev = next;
prev = curr;
curr = next;
}
return prev;
}
// 打印双链表函数
void printList(ListNode* head) {
while (head != NULL) {
printf("%d ", head->val);
head = head->next;
}
printf("\n");
}
int main() {
// 创建双链表
ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
node1->val = 1;
ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
node2->val = 2;
ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
node3->val = 3;
ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
node4->val = 4;
node1->next = node2;
node2->prev = node1;
node2->next = node3;
node3->prev = node2;
node3->next = node4;
node4->prev = node3;
node4->next = NULL;
// 打印原始双链表
printf("Original List: ");
printList(node1);
// 反转双链表
ListNode* newHead = reverseList(node1);
// 打印反转后的双链表
printf("Reversed List: ");
printList(newHead);
return 0;
}
```
代码解析:
1. 定义了一个双链表节点结构体,包括节点值、下一个节点指针和上一个节点指针。
2. 定义了一个反转双链表的函数,参数为头节点指针,返回值为反转后的头节点指针。
3. 在反转双链表函数中,定义了三个指针变量,分别代表前一个节点、当前节点和下一个节点。初始时,前一个节点为NULL,当前节点为头节点。
4. 使用while循环遍历整个双链表,每次迭代时,先将当前节点的下一个节点保存到next指针中,然后将当前节点的next指针指向前一个节点,将prev指针指向next节点,更新前一个节点为当前节点,当前节点为next节点。
5. 最后返回前一个节点,即为反转后的头节点。
6. 定义了一个打印双链表的函数,参数为头节点指针,直接遍历整个链表,打印每个节点的值。
7. 在main函数中,创建了一个包含4个节点的双链表,并打印原始链表。
8. 调用反转双链表函数,得到反转后的链表头节点指针,并打印反转后的链表。
c语言实现双向链表反转
在C语言中,实现双向链表的反转通常涉及到三个指针节点:当前节点、前一个节点和下一个节点。以下是步骤简单的算法:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义双向链表节点结构
struct Node {
int data;
struct Node* prev; // 指向前一个节点
struct Node* next; // 指向后一个节点
};
void reverseList(struct Node** head) {
if (*head == NULL || (*head)->next == NULL) { // 如果链表为空或只有一个元素
return;
}
struct Node* current = *head;
struct Node* temp = NULL; // 临时变量用于交换节点
while (current != NULL) {
temp = current->prev; // 保存当前节点的前一个节点
current->prev = current->next; // 将当前节点的prev指向next
current->next = temp; // 将当前节点的next指向前一个节点(即反转)
current = current->prev; // 更新当前节点为新的prev
}
*head = temp; // 最终头节点变为原链表的最后一个节点
}
// 打印链表
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
printf("\n");
}
int main() {
// 创建并初始化双向链表...
// ...
// 反转链表
reverseList(&head);
// 输出反转后的链表
printList(head);
return 0;
}
```
在这个例子中,`reverseList`函数接受双向链表头节点的地址,并通过迭代遍历整个链表,在每次迭代中将两个相邻节点的位置互换。当遍历结束后,原来的头节点变成了原来的尾节点,完成了链表的反转。
阅读全文