单链表反转：迭代与递归两种解法详解

1. 题目背景与核心需求反转链表是数据结构与算法中的经典问题也是技术面试中的高频考点。LeetCode第206题要求我们将一个单链表的所有节点顺序完全反转并返回反转后的链表头节点。这个题目之所以被标记为hot100是因为它同时考察了程序员对指针操作Java中即引用操作的掌握程度以及迭代和递归两种不同思维模式的实现能力。在实际工程中链表反转也是某些特定场景下的基础操作比如某些LRU缓存实现、区块链的区块连接等场景都会用到类似逻辑。2. 迭代解法详解2.1 迭代思路拆解迭代法的核心思想是逐个遍历原链表节点在遍历过程中逐步改变节点的指向关系。我们需要维护三个关键指针prev指向已经反转部分的链表头current当前待处理节点next保存current的下一个节点防止断链public ListNode reverseList(ListNode head) { ListNode prev null; ListNode current head; while (current ! null) { ListNode next current.next; // 先保存下一个节点 current.next prev; // 反转当前节点指向 prev current; // prev移动到当前节点 current next; // current移动到下一个节点 } return prev; // 最后prev就是新链表的头 }2.2 迭代法执行过程示例以链表 1→2→3→null 为例初始状态prevnull, current1第一轮循环next21.nextnullprev1, current2此时链表1→null 和 2→3→null第二轮循环next32.next1prev2, current3链表2→1→null 和 3→null第三轮循环nextnull3.next2prev3, currentnull最终链表3→2→1→null2.3 迭代法注意事项边界处理空链表直接返回null循环终止条件current为null时停止必须先用next保存current.next否则反转后无法找到原链表的下个节点时间复杂度O(n)空间复杂度O(1)3. 递归解法详解3.1 递归思路拆解递归法的核心思想是假设后续链表已经反转成功只需要处理当前节点与后续部分的关系。这是一种自顶向下的思考方式基线条件链表为空或只有一个节点时直接返回递归反转head.next之后的链表将head.next的next指向head形成反转将head.next置为null避免循环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; }3.2 递归执行过程解析继续以1→2→3→null为例递归到最深层处理节点3时满足head.nextnull返回3回到节点2newHead32.next.next2 → 3→22.nextnull → 断开2→3回到节点1newHead31.next.next1 → 2→11.nextnull → 断开1→2最终得到3→2→1→null3.3 递归法注意事项递归深度与链表长度成正比长链表可能导致栈溢出必须正确处理基线条件否则会无限递归时间复杂度O(n)空间复杂度O(n)递归栈空间理解递归的关键是明确每一层递归都假设后续链表已经处理完毕4. 两种解法的对比与选择4.1 性能对比维度迭代法递归法时间复杂度O(n)O(n)空间复杂度O(1)O(n)适用场景长链表短链表代码可读性中等较高4.2 选择建议生产环境优先选择迭代法更节省内存面试时可以两种都实现展示全面能力递归法代码更简洁但需要理解递归思维当链表长度可能很大时如超过1000必须使用迭代法5. 常见错误与调试技巧5.1 典型错误案例丢失节点引用// 错误写法没有保存next就反转 while (current ! null) { current.next prev; // 此时丢失了原current.next prev current; current current.next; // 这里current已经是prev了 }递归基线条件不全// 只检查headnull可能NPE if (head null) return null;未断开原链接// 递归法中忘记head.nextnull head.next.next head; // 缺少 head.next null;5.2 调试技巧对于迭代法可以在循环中打印prev/current的值对于递归法可以使用递归深度参数辅助打印void reverse(ListNode head, int depth) { System.out.println( .repeat(depth) 处理节点 head.val); // ... }画图辅助在纸上画出每个步骤的指针变化使用LeetCode的链表可视化工具6. 算法扩展与变种6.1 反转链表的一部分反转从位置m到n的链表LeetCode 92题先遍历到m-1位置反转m到n的节点重新连接头尾部分6.2 K个一组反转链表每k个节点一组进行反转LeetCode 25题先计算链表长度分段进行反转连接各段6.3 双向链表反转相比单链表还需要处理prev指针Node reverse(Node head) { Node temp null; Node current head; while (current ! null) { temp current.prev; current.prev current.next; current.next temp; current current.prev; // 注意这里移动的是prev } return temp ! null ? temp.prev : head; }7. 工程实践中的应用内存管理某些内存池实现会用到链表反转撤销操作文本编辑器中的undo操作可能需要反向遍历区块链新区块总是添加到链首但某些查询需要反向遍历LRU缓存淘汰最久未使用时可能需要反转访问顺序实际开发中Java更常用ArrayList而非LinkedList。但当需要频繁在头部插入/删除时反转后的链表可能更高效。8. 个人实现心得指针/引用操作是核心建议先用小例子3个节点在纸上画图理解递归写法虽然简洁但要注意栈溢出问题迭代法的指针命名很重要prev/current/next比p1/p2/p3更易读链表问题通用的调试技巧打印节点值和next值添加辅助可视化方法使用单元测试验证边界条件在多次面试中我发现面试官常常会先让实现迭代法然后问能不能用递归实现。因此建议两种写法都要熟练掌握。对于Java开发者而言特别要注意null检查和对象引用的问题这与C/C的指针操作有些微妙的差异。