链表反转算法详解
📋 目录
- 算法概述
- 核心思想
- 三指针法详解
- 代码实现
- 指针操作详解
- 常见疑问解答
- 算法复杂度分析
- 扩展应用
🎯 算法概述
问题描述
示例
原始链表：1 -> 2 -> 3 -> NULL反转后： 3 -> 2 -> 1 -> NULL算法特点
- 时间复杂度: O(n)
- 空间复杂度: O(1)
- 核心算法: 三指针法
- 适用场景: 单链表反转
💡 核心思想
基本思路
通过三个指针（prev、current、next）逐步反转每个节点的指向关系。
反转过程
- 保存下一个节点：防止丢失后续节点信息
- 反转当前节点：让当前节点指向前一个节点
- 移动指针：准备处理下一个节点
- 重复过程：直到处理完所有节点
关键理解
- 每次只处理一个节点
- 通过改变节点的next指针实现反转
- 需要临时保存下一个节点地址
🔄 三指针法详解
三个指针的作用
1. prev指针
struct Node* prev = NULL; // 前一个节点指针- 作用：指向已反转部分的最后一个节点
- 初始值：NULL（第一个节点反转后指向NULL）
- 更新：每次循环后指向当前处理的节点
2. current指针
struct Node* current = head; // 当前处理节点指针- 作用：指向正在处理的节点
- 初始值：head（链表头节点）
- 更新：每次循环后移动到下一个节点
3. next指针
struct Node* next = NULL; // 下一个节点指针- 作用：临时保存下一个节点的地址
- 初始值：NULL
- 更新：每次循环开始时保存current->next
指针关系图
初始状态：prev=NULL current=head next=NULL ↓ ↓ ↓ NULL -> 1 -> 2 -> 3 -> NULL第1次循环后：prev=1 current=2 next=2 ↓ ↓ ↓NULL 3 -> NULL第2次循环后：prev=2 current=3 next=3 ↓ ↓ ↓NULL <- 1 NULL第3次循环后：prev=3 current=NULL next=NULL ↓ ↓ ↓NULL <- 1 <- 2 <- 3💻 代码实现
完整代码
#include #include // 定义链表的节点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;}// 打印链表void printList(struct Node* head) { struct Node* temp = head; while (temp != NULL) { printf(\"%d -> \", temp->data); temp = temp->next; } printf(\"NULL\\n\");}// 🎯 链表反转算法 - 核心函数struct Node* reverseList(struct Node* head) { // 三个指针：前一个、当前、下一个 struct Node* prev = NULL; // 前一个节点，初始为空 struct Node* current = head; // 当前节点，从头开始 struct Node* next = NULL; // 下一个节点，初始为空 printf(\"\\n=== 开始反转链表 ===\\n\"); printf(\"初始状态: prev=NULL, current=%d, next=NULL\\n\", current->data); // 只要当前节点不为空，就继续循环 while (current != NULL) { printf(\"\\n--- 处理节点 %d ---\\n\", current->data); // 第1步：保存下一个节点（因为改变current->next后会丢失） next = current->next; printf(\"第1步: next = current->next = %s\\n\", next == NULL ? \"NULL\" : \"下一个节点\"); // 第2步：反转指针（让当前节点指向前一个） current->next = prev; printf(\"第2步: current->next = prev = %s\\n\", prev == NULL ? \"NULL\" : \"前一个节点\"); // 第3步：移动prev指针 prev = current; printf(\"第3步: prev = current = %d\\n\", current->data); // 第4步：移动current指针 current = next; printf(\"第4步: current = next = %s\\n\", current == NULL ? \"NULL\" : \"下一个节点\"); // 打印当前状态 printf(\"当前状态: \"); if (prev != NULL) { printf(\"已反转部分: \"); struct Node* temp = prev; while (temp != NULL) { printf(\"%d\", temp->data); if (temp->next != NULL) printf(\" <- \"); temp = temp->next; } } printf(\" | 剩余部分: \"); if (current != NULL) { struct Node* temp = current; while (temp != NULL) { printf(\"%d\", temp->data); if (temp->next != NULL) printf(\" -> \"); temp = temp->next; } } else { printf(\"NULL\"); } printf(\"\\n\"); } printf(\"\\n反转完成！返回prev指向的节点\\n\"); return prev; // prev现在指向新的头节点}// 释放链表内存void freeList(struct Node* head) { struct Node* current = head; while (current != NULL) { struct Node* next = current->next; free(current); current = next; }}int main() { printf(\"=== 链表反转算法详细演示 ===\\n\\n\"); // 创建3个节点：5 -> 8 -> 12 -> NULL printf(\"1. 创建原始链表:\\n\"); struct Node* head = createNode(5); head->next = createNode(8); head->next->next = createNode(12); printf(\"原始链表: \"); printList(head); // 反转链表 printf(\"\\n2. 执行反转算法:\\n\"); struct Node* reversedHead = reverseList(head); // 打印反转后的结果 printf(\"\\n3. 反转结果:\\n\"); printf(\"反转后链表: \"); printList(reversedHead); // 验证反转是否正确 printf(\"\\n4. 验证结果:\\n\"); printf(\"原始: 5 -> 8 -> 12 -> NULL\\n\"); printf(\"反转: 12 -> 8 -> 5 -> NULL\\n\"); printf(\"结果: %s\\n\", (reversedHead->data == 12 && reversedHead->next->data == 8 && reversedHead->next->next->data == 5) ? \"✅ 正确\" : \"❌ 错误\"); // 释放内存 freeList(reversedHead); return 0;}核心算法简化版
struct Node* reverseList(struct Node* head) { struct Node* prev = NULL; struct Node* current = head; struct Node* next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转指针 prev = current; // 移动prev指针 current = next; // 移动current指针 } return prev;}🔍 指针操作详解
1. 两个不同的\"next\"
变量next vs 结构体成员next
struct Node* next = NULL; // 这是一个变量，用来保存地址current->next // 这是结构体Node的成员，指向下一个节点区别：
- 变量
next：临时保存器，用来记住下一个节点的地址 - 结构体成员
next：链表节点之间的连接器，指向下一个节点
更清晰的命名建议
struct Node* nextNode = NULL; // 更清晰的变量名struct Node* current = head;while (current != NULL) { nextNode = current->next; // 保存下一个节点 current->next = prev; // 反转指针 prev = current; current = nextNode;}2. 四步操作详解
第1步：next = current->next;
next = current->next;作用：保存下一个节点的地址
原因：因为下一步要修改current->next，如果不先保存就会丢失信息
第2步：current->next = prev;
current->next = prev;作用：反转当前节点的指向
结果：当前节点指向前一个节点
第3步：prev = current;
prev = current;作用：更新prev指针
结果：prev指向当前已处理的节点
第4步：current = next;
current = next;作用：移动current指针到下一个节点
结果：准备处理下一个节点
3. 为什么需要四步？
反转指针 vs 移动指针
-
反转指针（
current->next = prev）：- 改变节点的连接关系
- 实现链表反转
-
移动指针（
current = next）：- 让处理指针移动到下一个节点
- 确保算法能够继续处理所有节点
如果不移动current会发生什么？
while (current != NULL) { next = current->next; current->next = prev; // 反转指针 prev = current; // current = next; // 如果注释掉这行 // 问题：current还是指向同一个节点 // 下次循环会重复处理同一个节点 // 导致无限循环！}❓ 常见疑问解答
Q1: 为什么需要保存next？
A: 因为修改current->next后会丢失下一个节点的信息，需要先保存。
Q2: 反转指针后为什么还要移动current？
A: 反转指针只是改变了连接关系，移动current是为了处理下一个节点，避免重复处理。
Q3: prev指针的作用是什么？
A: prev指向已反转部分的最后一个节点，新反转的节点需要指向它。
Q4: 为什么最后返回prev？
A: 循环结束后，prev指向原链表的最后一个节点，即新链表的头节点。
Q5: 空链表怎么处理？
A: 如果head为NULL，while循环不会执行，直接返回prev（NULL）。
Q6: 只有一个节点的链表怎么处理？
A: 第一次循环后，current变为NULL，循环结束，返回prev指向的节点。
📊 算法复杂度分析
时间复杂度
- O(n)：需要遍历链表中的每个节点一次
- n为链表的节点数量
空间复杂度
- O(1)：只使用了三个指针变量，空间使用量固定
性能特点
- 优点：空间效率高，原地反转
- 缺点：无法并行处理
- 适用性：适合大多数单链表反转场景
🚀 扩展应用
1. 反转链表的一部分
// 反转从第m个节点到第n个节点的部分struct Node* reverseBetween(struct Node* head, int m, int n) { if (head == NULL || m >= n) return head; struct Node* dummy = createNode(0); dummy->next = head; struct Node* prev = dummy; // 移动到第m个节点的前一个节点 for (int i = 1; i < m; i++) { prev = prev->next; } // 反转从第m个到第n个节点 struct Node* current = prev->next; for (int i = m; i < n; i++) { struct Node* next = current->next; current->next = next->next; next->next = prev->next; prev->next = next; } return dummy->next;}2. K个一组反转链表
// 每K个节点为一组进行反转struct Node* reverseKGroup(struct Node* head, int k) { if (head == NULL || k <= 1) return head; struct Node* current = head; int count = 0; // 检查是否有足够的节点 while (current != NULL && count < k) { current = current->next; count++; } if (count < k) return head; // 不足K个节点，不反转 // 反转前K个节点 struct Node* prev = NULL; current = head; for (int i = 0; i < k; i++) { struct Node* next = current->next; current->next = prev; prev = current; current = next; } // 递归处理剩余节点 head->next = reverseKGroup(current, k); return prev;}3. 判断链表是否有环
// 使用快慢指针判断链表是否有环bool hasCycle(struct Node* head) { if (head == NULL || head->next == NULL) return false; struct Node* slow = head; struct Node* fast = head->next; while (slow != fast) { if (fast == NULL || fast->next == NULL) return false; slow = slow->next; fast = fast->next->next; } return true;}📝 总结
算法要点
- 三指针法：prev、current、next三个指针协同工作
- 四步操作：保存、反转、更新、移动
- 原地反转：不需要额外空间
- 一次遍历：时间复杂度O(n)
关键理解
- 每次只处理一个节点
- 通过改变next指针实现反转
- 需要临时保存下一个节点地址
- 反转和移动是两个不同的操作
应用场景
- 链表操作基础算法
- 面试常见题目
- 其他链表算法的基础
🔗 相关资源
学习资源
- LeetCode 206 - 反转链表
- 数据结构与算法教程
- 链表操作详解
扩展题目
- 反转链表的一部分
- K个一组反转链表
- 判断链表是否有环
- 找到链表的中间节点
本文档最后更新: 2024年
适用于: 数据结构与算法学习
维护者: 算法学习团队
