链表反转是数据结构与算法中的经典问题，也是面试中的高频考点。这个问题看似简单，却能考察程序员对指针操作、递归思维和边界条件的处理能力。在本文中，我们将深入探讨链表反转的两种经典解法：迭代法和递归法，并提供详细的代码实现和优化技巧。
问题描述
给定一个单链表的头节点head，要求返回反转后的链表。
示例：
text
输入: 1 → 2 → 3 → 4 → 5 → null 输出: 5 → 4 → 3 → 2 → 1 → null
方法一：迭代法（推荐）
核心思想
通过两个指针pre和cur遍历链表，在遍历过程中逐个反转节点间的指针方向。
算法步骤
初始化两个指针：
pre = null,cur = head遍历链表，直到
cur为 null：保存
cur的下一个节点：temp = cur.next反转指针：
cur.next = pre移动指针：
pre = cur,cur = temp
返回
pre（新的头节点）
代码实现
public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { // 保存下一个节点，防止断链 ListNode temp = cur.next; // 反转指针 cur.next = pre; // 移动指针 pre = cur; cur = temp; } return pre; }图解过程
text
初始状态： pre = null, cur = 1 → 2 → 3 → 4 → null 第1次循环： temp = 2 1.next = null pre = 1, cur = 2 结果：null ← 1 2 → 3 → 4 → null 第2次循环： temp = 3 2.next = 1 pre = 2, cur = 3 结果：null ← 1 ← 2 3 → 4 → null 第3次循环： temp = 4 3.next = 2 pre = 3, cur = 4 结果：null ← 1 ← 2 ← 3 4 → null 第4次循环： temp = null 4.next = 3 pre = 4, cur = null 结果：null ← 1 ← 2 ← 3 ← 4 结束循环，返回pre=4
复杂度分析
时间复杂度：O(n)，每个节点只遍历一次
空间复杂度：O(1)，只使用了固定的几个指针变量
方法二：递归法
核心思想
利用递归的栈结构，从链表的尾部开始反转，先反转后面的部分，再处理当前节点。
算法步骤
递归终止条件：链表为空或只有一个节点
递归反转以
head.next为头节点的子链表将当前节点连接到已反转的子链表的尾部
返回新的头节点
代码实现
public ListNode reverseList(ListNode head) { // 递归终止条件 if (head == null || head.next == null) { return head; } // 递归反转后续链表 ListNode newHead = reverseList(head.next); // 将当前节点连接到反转后的链表尾部 head.next.next = head; head.next = null; return newHead; }图解递归过程
text
初始链表：1 → 2 → 3 → 4 → null 递归调用栈： reverse(1)调用reverse(2) reverse(2)调用reverse(3) reverse(3)调用reverse(4) reverse(4)返回4（base case） 开始回溯： reverse(3)中：3.next.next = 3，即4.next = 3 3.next = null 返回newHead=4（链表：4 → 3 → null） reverse(2)中：2.next.next = 2，即3.next = 2 2.next = null 返回newHead=4（链表：4 → 3 → 2 → null） reverse(1)中：1.next.next = 1，即2.next = 1 1.next = null 返回newHead=4（链表：4 → 3 → 2 → 1 → null）
复杂度分析
时间复杂度：O(n)，每个节点处理一次
空间复杂度：O(n)，递归调用栈的深度为n
两种方法的对比
| 特性 | 迭代法 | 递归法 |
|---|---|---|
| 时间复杂度 | O(n) | O(n) |
| 空间复杂度 | O(1) | O(n)（递归栈） |
| 代码简洁性 | 中等 | 简洁优雅 |
| 理解难度 | 较易 | 较难（需要理解递归） |
| 适用场景 | 链表较长时 | 链表较短或需要简洁实现时 |
常见错误与陷阱
错误1：指针丢失
java
// 错误的写法 while (cur != null) { cur.next = pre; // 直接修改cur.next，丢失了下一个节点 pre = cur; cur = cur.next; // cur.next已经是pre，导致循环异常 }解决方法：在修改指针前，先用临时变量保存下一个节点。
错误2：空指针异常
java
// 错误的写法 ListNode temp = cur.next; // 如果cur为null，这里会抛异常 while (cur != null) { // ... }解决方法：确保在访问节点属性前进行空值检查。
错误3：忘记处理原头节点的next指针
在递归法中，如果不将原头节点的next设为null，会导致链表成环。
变体问题
1. 反转链表的一部分（比如反转中间到最后，那要先找到中间位置：快慢指针）
反转链表中从位置m到n的部分。
解题思路：
找到第
m-1个节点（连接点）反转
m到n的节点重新连接三部分
2. K个一组反转链表
每k个节点一组进行反转，最后不足k个的保持原样。
解题思路：
统计链表长度
按组进行反转
递归或迭代处理剩余部分
3. 反转相邻节点
交换相邻的两个节点。
解题思路：
使用虚拟头节点，每次处理两个节点。
面试技巧
先画图：在面试中，先用简单的例子画图说明思路
考虑边界：空链表、单节点链表、双节点链表
测试用例：
null（空链表）1 → null（单节点）1 → 2 → null（双节点）1 → 2 → 3 → 4 → 5 → null（多节点）
复杂度分析：主动分析时间和空间复杂度
代码优化：写出代码后，思考是否有优化空间
实际应用场景
浏览器历史记录：前进后退功能需要类似的反转操作
撤销操作：文本编辑器中的撤销功能
内存管理：某些垃圾回收算法中
数据同步：双向同步的数据结构
扩展学习
双向链表反转：需要同时处理
prev和next指针环形链表反转：需要特别注意环的断开与连接
原地反转数组：类似的思想可以应用于数组
总结
链表反转是掌握指针操作的基础，通过这个问题可以深入理解：
指针的移动与修改
递归思维的应用
边界条件的处理
时间与空间复杂度的权衡
建议初学者先从迭代法开始理解，掌握指针的操作技巧，再尝试理解递归法的精妙之处。在实际工程中，迭代法通常更受欢迎，因为它没有递归的栈溢出风险，且空间效率更高。
记住：理解一个算法的最好方式是多画图、多写代码、多思考边界情况。希望这篇文章能帮助你彻底掌握链表反转问题！
