Q206 反转链表

题目：给你单链表的头节点 head，请你反转链表，并返回反转后的链表。输入：1 → 2 → 3 → 4 → 5，输出：5 → 4 → 3 → 2 → 1。

1 简要回答

递归版把问题拆成两步：

1
2

反转 1→2→3→4
= 先反转 2→3→4（得到 4→3→2），再把 1 接到 2 的后面

• 每次递归返回：反转后链表的头节点（也就是原链表的尾节点，全程不变）。
• 自己这一层只做两件事：head->next->next = head（把原后继反过来指向自己）、head->next = nullptr（断开旧指针，防止成环）。
• 时间复杂度 $O(n)$，空间复杂度 $O(n)$（递归栈深度）。

2 递归三步法：把它当成数学归纳法

1. 基例：空链表或只有一个节点，反转后还是它自己，直接返回。
2. 假设子问题已解决：reverseList(head->next) 返回的 last，就是 head 后面那段链表反转后的新头。
3. 只处理自己：把 head 挂到新链表末尾，并断开原来的 next。

关键是第 2 步的"信任"。递归不是让你跟踪每一层调用，而是假设"更短的链表已经被别人正确反转好了"。

1
2
3
4
5
6
7
8
9

ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;                          // 基例
    }
    ListNode* last = reverseList(head->next); // 假设后面已经反转好
    head->next->next = head;                  // 把自己挂到末尾
    head->next = nullptr;                     // 断开旧指针
    return last;                              // 新头始终不变
}

2.1 为什么 head->next->next = head 就完成了"挂到末尾"

递归返回后，head->next 仍然是原来的后继节点，但它已经变成反转后子链表的最后一个节点：

1
2
3

反转前：          head → head->next → ... → last
调用后（还没处理 head 时）：
                  head → (4 → 3 → 2)        ← head->next 现在指向 2，正好是子链表尾巴

所以 head->next->next = head 的意思是：“让子链表的尾巴再指向我”，于是 head 就被接到了末尾。

2.2 完整回溯过程（1 → 2 → 3 → 4）

递归先一路走到 4，返回 4（基例）。然后从 3 开始逐层往回处理：

最终：4→3→2→1→∅，返回的 last 一直是 4。

关键直觉：每个节点在回溯时只做一件小事——“让后面的节点指回我，然后我断掉旧指针”。所有节点都做完，整条链就反过来了。

3 迭代版（对照组）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;  // 先保存下一个，防止断链
        cur->next = pre;             // 反转当前指针
        pre = cur;                   // pre 前进
        cur = next;                  // cur 前进
    }
    return pre;                      // 结束时 pre 是原链表尾，即新链表头
}

迭代版是"从前往后"逐条改箭头；递归版是"从后往前"逐层改箭头，顺序正好相反。

4 双指针改递归：不靠想象，靠机械改写

如果"信任"递归有困难，别急着理解经典版。把迭代版机械改写成递归，两者完全等价，每一步都摊在明面上。

改写只有四条规则：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

ListNode* reverse(ListNode* pre, ListNode* cur) {
    if (cur == nullptr) return pre;      // 循环退出条件
    ListNode* temp = cur->next;          // 保存下一个，防止断链
    cur->next = pre;                     // 反转当前指针
    return reverse(cur, temp);           // 相当于 pre = cur; cur = temp; 进入下一轮
}

ListNode* reverseList(ListNode* head) {
    return reverse(nullptr, head);       // 相当于 pre = nullptr; cur = head;
}

把它展开看，就是一串循环：

1

reverse(NULL, 1) → reverse(1, 2) → reverse(2, 3) → reverse(3, 4) → reverse(4, NULL)

最后一层 cur == NULL 返回 pre（就是 4），一路原样传回，和迭代版 return pre 完全一致。

信任的本质：递归不需要你"想象"全过程，只需要验证两件事——基例对不对（空链表或最后一个节点返回正确），当前层在子问题正确的假设下对不对。两个都验证过，递归就永远正确。

经典版里 reverseList(head->next) 返回的 last，就是"循环跑完时的 pre"，全程不变。

5 虚拟头 + 头插法：把每个节点变成同一种节点

加一个虚拟头 dummy，每次把当前节点插到 dummy 后面（头插），所有节点的操作完全一样，不用特判头节点：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

ListNode* reverseList(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    while (head != nullptr) {
        ListNode* next = head->next;   // 保存下一个，防止断链
        head->next = dummy->next;      // 把当前节点插到 dummy 后面
        dummy->next = head;
        head = next;
    }
    return dummy->next;                // dummy 站岗，dummy->next 交卷
}

用 1→2→3 走一遍：

1
2
3
4

dummy → 1              （插 1）
dummy → 2 → 1          （插 2）
dummy → 3 → 2 → 1      （插 3）
返回 3 → 2 → 1

和 pre = nullptr 的写法是同一个思想：nullptr/虚拟头让"第一个节点"也被统一处理。这套头插法也是反转区间、K 个一组反转的基础。

易错：② 让新节点先接住"当前最前面的节点"（已反转的那段链），③ 才把新节点放到最前面。顺序不能反：先 ③ 后 ② 会让新节点的 next 指向自己，成环。规则和"改指针前先保存/接好后面的链"是同一个——先接后面，再改前面。

6 易错点

• 忘记 head->next = nullptr：1→2→1 会成环，遍历直接死循环。head->next->next = head; 和 head->next = nullptr; 必须成对出现。
• 返回了 head 而不是 last：会得到"局部反转 + 后半段丢失"的错链。
• 基例只写 head == nullptr 不够：单节点链表也要直接返回，否则 head->next->next 会解引用空指针。
• 链表很长（如 $10^5$ 级）时递归会爆栈，工程上优先用迭代。

6.1 遇到 AddressSanitizer: heap-use-after-free 怎么定位

LeetCode 判题器跑完你的代码后会释放链表（freeList）。如果反转后的链表里有环，freeList 会先删掉某个节点，稍后又从环的另一条路走到这个已经删除的节点——于是报 heap-use-after-free（读到了已释放的内存）。

读报错三步：

1. 看错误类型和位置：heap-use-after-free + 出错函数是 freeList → 不是你的代码当场崩，而是返回的链表结构坏了。
2. 想 freeList 怎么写的：while (head) { next = head->next; delete head; head = next; }——它会读 head->next，只有链表成环（或一个节点被两条链指着）才会读到已删除节点的 next。
3. 回代码找"谁可能制造环"：反转链表里制造反向指针的是 head->next->next = head，如果不同时 head->next = nullptr，就成了 1→2→1 的环。

细节：报错里的 16-byte region 正好是一个 ListNode（val + next 各 8 字节），READ of size 8 读的正是 next 指针。这些信息都在印证：freeList 走到一个被删过的节点上了。

自查方法：本地打印反转后的链表，最多走 $n+1$ 步；如果没遇到 nullptr 还在走，就是环。