1、使用两个指针反转链表
可以只使用两个指针反转一个单向链表,但逻辑会稍微复杂一点。我们可以通过巧妙地在迭代过程中更新指针,达到反转链表的效果。
#include <stdio.h> #include <stdlib.h> // 定义节点结构 struct Node { int data; struct Node* next; }; // 创建新节点 struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // 反转链表(使用两个指针) struct Node* reverseList(struct Node* head) { struct Node* prev = NULL; struct Node* curr = head; while (curr != NULL) { struct Node* next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } // 打印链表 void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 释放链表 void freeList(struct Node* head) { while (head != NULL) { struct Node* temp = head; head = head->next; free(temp); } } int main() { // 创建链表 1->2->3->4->NULL struct Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); printf("原始链表: "); printList(head); // 反转链表 head = reverseList(head); printf("反转后的链表: "); printList(head); // 释放内存 freeList(head); return 0; }
标准写法略作修改
在每次循环中用一个临时变量交换两个指针的含义,达到节省第三个指针的目的。
#include <stdio.h> #include <stdlib.h> #include <stdint.h> // 定义节点结构 struct Node { int data; struct Node* next; }; // 创建新节点 struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // 反转链表(使用两个指针) struct Node* reverseList(struct Node* head) { struct Node* prev = NULL; struct Node* curr = head; while (curr) { curr = (struct Node*)((uintptr_t)curr->next ^ (uintptr_t)prev); // 上面是技巧性的 XOR 计算。不是推荐方式。 } return prev; } // 打印链表 void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 释放链表 void freeList(struct Node* head) { while (head != NULL) { struct Node* temp = head; head = head->next; free(temp); } } int main() { // 创建链表 1->2->3->4->NULL struct Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); printf("原始链表: "); printList(head); // 反转链表 head = reverseList(head); printf("反转后的链表: "); printList(head); // 释放内存 freeList(head); return 0; }
2、 更清晰、可读的标准方式(推荐使用三个指针)
使用三个指针 (previous
, current
, next
) 的标准方式通常被认为更清晰和可读,因为它在每一步都显式地维护了当前节点、前一个节点和下一个节点的引用,使得链表的反转过程更加直观易懂。
#include <stdio.h> #include <stdlib.h> #include <stdint.h> // 定义节点结构 struct Node { int data; struct Node* next; }; // 创建新节点 struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } // 反转链表(三个指针) struct Node* reverseList(struct Node* head) { struct Node* prev = NULL; struct Node* curr = head; struct Node* next = NULL; while (curr != NULL) { next = curr->next; // 暂存下一个节点 curr->next = prev; // 反转指针 prev = curr; // 向前推进 curr = next; } return prev; // 新的头结点 } // 打印链表 void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf("%d -> ", temp->data); temp = temp->next; } printf("NULL\n"); } // 释放链表 void freeList(struct Node* head) { while (head != NULL) { struct Node* temp = head; head = head->next; free(temp); } } int main() { // 创建链表 1->2->3->4->NULL struct Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); printf("原始链表: "); printList(head); // 反转链表 head = reverseList(head); printf("反转后的链表: "); printList(head); // 释放内存 freeList(head); return 0; }