CS-Notes 剑指 Offer 24 反转链表：递归与头插法迭代两种解法的完整解析

本篇基于 剑指 Offer 24 反转链表 的题解文档，完整覆盖递归与迭代（头插法）两种实现，并结合 CS-Notes 仓库中 Leetcode 题解 - 链表、从尾到头打印链表 等文档中的实现细节，把每一行指针操作的作用、边界条件与复杂度逐一讲透。读完后你将能够独立写出并解释这两种反转链表的方案，并理解头插法在其它链表题目中的通用用法。

题目描述

给出一个链表的头节点 head，要求反转该链表并返回反转后的头节点。题目只允许通过操作 next 指针来改变结构，而不能直接读写节点里的值（这是剑指 Offer 版本题源的经典约束，对应 Leetcode 206. Reverse Linked List (Easy)）。

从 CS-Notes 剑指 Offer 题解目录（剑指 Offer 题解 - 目录）可以看到，第 24 题位于第 18 题（删除链表节点）、第 22 题（链表中倒数第 K 个结点）、第 23 题（链表中环的入口结点）之后，紧接着是第 25 题（合并两个排序的链表），属于链表操作的基础必会题：反转操作本身是大量链表题（如回文链表、K 个一组翻转）的底层构件。

解法一：递归

原文档给出的递归解法如下：

public ListNode ReverseList(ListNode head) {
    if (head == null || head.next == null)
        return head;
    ListNode next = head.next;
    head.next = null;
    ListNode newHead = ReverseList(next);
    next.next = head;
    return newHead;
}

逐行拆解其执行逻辑：

1. 递归终止条件：head == null || head.next == null。空链表或只有一个节点时，反转结果就是它自己，直接返回。
2. 保存后继：next = head.next 先把当前节点的下一个节点存下来，否则下一步断开指针后会丢失链尾。
3. 断开当前节点：head.next = null。这是递归版的一个关键细节——先把当前节点与后继断开，让它暂时成为新链表的尾节点，避免将来出现双指向或环。Leetcode 题解 - 链表 中给出的同思路写法把 head.next = null 放在 next.next = head 之后，两种顺序在功能上等价（都保证了 head 不会与后继互指），只是断开时点不同。
4. 递归反转子链：newHead = ReverseList(next)。把 next 之后的所有节点反转，拿到反转后子链的新头节点。
5. 接回当前节点：next.next = head。此时 next 是反转后子链的尾节点，让它指回当前节点，head 就被挂到了整个链表的最末端。
6. 返回新头：每一层都返回同一份 newHead（即原链表尾节点），最终顶层调用拿到完整的反转头节点。

以 1 -> 2 -> 3 为例，递归展开过程是：先到达 3 返回，然后 2 接上 3 并返回 3，最后 1 接上 2，得到 3 -> 2 -> 1 -> null。

复杂度：时间 O(n)，每个节点访问一次；空间 O(n)，递归调用栈深度为链表长度 n。链表的递归解法本质上都是 O(n) 栈开销，链表很长时需要注意栈溢出风险，这也是面试中常考的追问点。

解法二：迭代（头插法）

原文档给出的迭代解法：

public ListNode ReverseList(ListNode head) {
    ListNode newList = new ListNode(-1);
    while (head != null) {
        ListNode next = head.next;
        head.next = newList.next;
        newList.next = head;
        head = next;
    }
    return newList.next;
}

这段代码的核心是头插法：引入一个不存值的辅助头结点 newList（哨兵节点），遍历原链表时，把当前节点逐个插到 newList 之后。由于每次都插在最前面，先遍历到的节点被排到最后，自然就实现了逆序。从尾到头打印链表 的文档中对头插法有专门解释：链表插入操作需要维护后继关系，通用的"在 node1 之后插入 node2"三步是 node2.next = node1.next; node1.next = node2;，头插法正是把"插入位置"固定为新链表头部。

循环体内四条语句的顺序不能乱，逐步对照 1 -> 2 -> 3 来看：

循环轮次	head 指向	执行 head.next = newList.next; newList.next = head; 后新链表状态	说明
第 1 轮	1	newList -> 1	1.next 先指向 newList.next（null），再让哨兵指回 1
第 2 轮	2	newList -> 2 -> 1	2.next 接到旧头 1，2 成为新头
第 3 轮	3	newList -> 3 -> 2 -> 1	同上，3 成为新头

其中 next = head.next 必须在改指针之前执行，否则 head.next = newList.next 会覆盖掉原后继，原链表从此断链。循环结束时 newList.next 即反转链表的真正头节点（第 1 个节点 3），这就是为什么返回 newList.next 而不是 newList。

复杂度：时间 O(n)，空间 O(1)，只用了指针和哨兵节点，没有额外数据结构，也没有递归栈。对于"反转链表"这类题目，迭代头插法通常是面试首选答案。

两种解法对比与易错点

维度	递归	迭代（头插法）
时间复杂度	O(n)	O(n)
空间复杂度	O(n)，调用栈	O(1)
核心动作	断开 head.next，递归后 next.next = head	哨兵 + 头插：head.next = newList.next; newList.next = head;
典型风险	长链表栈溢出	指针改序错误导致成环或丢链

结合两份文档的实现，可以归纳出三个高频易错点：

1. 先存后继，再改指针。无论递归还是迭代，第一句几乎都是 ListNode next = head.next;，一旦顺序颠倒，原链表的剩余部分就找不回来了。
2. 尾指针必须置空。递归版显式写了 head.next = null；迭代版中最后一个被插入的节点（原头节点）其 next 恰好指向 newList.next 当时的值（即 null），天然收尾。写递归时若漏掉断链，会得到 ... -> 1 <-> 2 的双向互指结构。
3. 哨兵节点不返回值本身。头插法返回的是 newList.next，哨兵 newList 只是辅助；把两者混淆是头插法写法最常见的 bug。

反转链表在其它题目中的复用

反转操作不是孤立的，CS-Notes 中多处直接复用了这一原语：

• Leetcode 题解 - 链表 的"回文链表"一题：用快慢指针切半后，return isEqual(head, reverse(slow)); 直接调用了 reverse 函数（同样用头插法实现：head.next = newHead; newHead = head;），验证了头插法是反转的通用模式；
• 从尾到头打印链表 的第 2 种解法：用完全相同的头插法先构建逆序链表再依次取值，说明"头插法逆序化"是独立的通用技巧，不只服务于"反转"题面；
• 剑指 Offer 25 合并两个排序的链表 与 52 两个链表的第一个公共结点 等后续链表题，也依赖对 next 指针的同类单步维护能力。

小结

• 递归解法靠"先断开、后接回"把当前节点挂到子链尾部，代码短但带 O(n) 栈开销；
• 迭代头插法靠哨兵节点 + 固定三步插入实现 O(1) 空间反转，是工程与面试的双重首选；
• 掌握这两种写法后，回文链表、K 个一组翻转等进阶题都只是"局部反转"的组合复用。