LeetCode 206 反转链表图解：四行指针的顺序，和递归版在长链上爆栈

LeetCode 206 的题面只有一句话：给你单链表的头节点，把整条链反过来，返回新的头。它是链表题的入门题，也是面试里被要求「写完再讲一遍」最多的题之一。难点不在思路，在于四行赋值的先后顺序。这篇把每一步的指针状态画出来，再拿递归版去撞一次栈的上限。

本系列其他篇目在 浏览器里的 C++，这里的代码都可以直接贴进 Playground 运行。

反转链表的思路一句话就能说完，出错几乎都出在赋值顺序上：如果先改 cur->next，再去取下一个节点，后半截链表就再也找不回来了。递归版代码更短，但每个节点占一层调用栈，额外空间是 O(n)。下文先逐步画出迭代版的指针状态，再在默认 8 MB 栈上测出递归版能处理的最长链。

三个指针各管什么

迭代写法要同时盯住三个位置：

• prev：已经反转好的那一段的头。一开始是空，因为还什么都没反转。
• cur：正在处理的节点。
• next：cur 原来的后继。它只活一轮，作用是在 cur->next 被改写之前，把剩下的链表抓在手里。

每一轮做四件事，顺序固定：

ListNode* next = cur->next;  // 1. 先记住后路
cur->next = prev;            // 2. 掉头
prev = cur;                  // 3. 已反转部分长了一格
cur = next;                  // 4. 去下一个

可以把它想成过河拆桥：先把下一块木板的位置记下来（第 1 行），再把脚下这块木板转向身后（第 2 行），然后人往前挪一步（第 3、4 行）。拆桥之前没记下一块在哪，人就被困在原地。

逐步状态：1→2→3→4→5

下面这张表是 Playground 程序对输入 1 2 3 4 5 的实际输出，整理成了表格。done 是从 prev 出发能走到的链，rest 是从 cur 出发能走到的链。

每一轮，rest 的第一个节点被摘下来，插到 done 的最前面。两段长度之和始终是 5，没有节点丢失，也没有节点被复制。循环在 cur 变成空时结束，此时 prev 指着原来的尾节点，就是新的头。

用图看第 3 轮做完之后的样子：

           prev          cur
            │             │
null ◀─ 1 ◀─ 2 ◀─ 3       4 ──▶ 5 ──▶ null

3 已经掉头指向 2。3 和 4 之间这时候没有任何指针相连，能找到 4 的只有 cur。这一刻如果 cur 没被正确赋值，4 和 5 就再也找不回来了。

顺序换一行会怎样

把第 1 行和第 2 行对调，先掉头再记后路：

cur->next = prev;
ListNode* next = cur->next;  // 这时候读到的是 prev，不是原来的后继

next 拿到的是刚写进去的 prev。第一轮 prev 是空，于是 cur 变成空，循环直接结束。本机用 g++ 14.2 和 clang++ 19.1 编译这一版，对 1 2 3 4 5 跑出来的结果都是只剩一个 1。2 到 5 这四个节点没有被释放，只是再也没有指针指向它们。如果它们是 new 出来的，这就是一次内存泄漏；在评测系统上，则是一个答案错误。

这类错误不会报错，也不会崩。它的症状是「结果短了」，所以调试时先打印长度，比打印内容更快发现问题。

递归版：短，但每个节点占一层栈

递归写法的想法是：先把 head 后面的部分整个反转，拿到新头；再让 head 的后继反过来指向 head。

1ListNode* reverse_rec(ListNode* head) {
2    if (!head || !head->next) return head;
3    ListNode* new_head = reverse_rec(head->next);
4    head->next->next = head;
5    head->next = nullptr;
6    return new_head;
7}

第 5 行最容易漏。漏掉它，原来的头节点 1 仍然指向 2，而 2 已经被改成指向 1，两个节点互相指着。本机实测漏掉这一行后，从新头往后走 10 步，打印出来的是 5 4 3 2 1 2 1 2 1 2，在 1 和 2 之间无限循环。Playground 里的打印函数设了步数上限，超过节点总数就输出 ...(cycle?)，就是为了把这种情况显示出来，而不是让程序转到 5 秒超时。

递归版的问题是深度。链表有多少个节点，调用就有多少层，每层都要在栈上留下返回地址和保存的寄存器。Linux 默认栈是 8 MB（ulimit -s 显示 8192），用二分搜索长度可以找出能跑通的最长链：

clang -O2 的数字最好解释：看汇编，函数里只有一条 push %rbx，加上 call 压的返回地址，正好 16 字节，8 MB 除以 16 就是 52 万多。

g++ -O2 的「不到 10 字节」比一个返回地址还小，这说明不是每个节点都对应一次真正的调用。它的汇编里有五条 push，一帧约 48 字节，按 87 万这个深度倒推，大约每次真正的调用处理了 5 个节点，也就是编译器把几层递归内联到了一起。这是优化器的选择，换个版本或换个开关就会变，不能当作保证。

同样的程序，迭代版在 1000 万个节点上照常跑完。它只用三个指针，额外空间是常数。

LeetCode 206 的数据范围是最多 5000 个节点，递归版在那里不会出事。但工程里的链表没有这个上限。一份日志、一条消息队列，长度由外部输入决定。默认用迭代版，是因为它的正确性不依赖输入规模。

在这里跑

程序读 n，再读 n 个整数建链，然后用迭代版反转，每一轮打印一次 done 和 rest。节点放在一个 std::vector 里，用下标顺序串起来，省去手动 delete。

本机 g++ 14.2 和 clang++ 19.1 都用 -O2 -Wall -Wextra 编译，无警告，默认 stdin 下两者输出逐字节相同：

input:  1->2->3->4->5
step 1: done=1  rest=2->3->4->5
step 2: done=2->1  rest=3->4->5
step 3: done=3->2->1  rest=4->5
step 4: done=4->3->2->1  rest=5
step 5: done=5->4->3->2->1  rest=null
output: 5->4->3->2->1

两个边界值得自己试一下。stdin 改成 0，输入输出都是 null，循环一次都不进，prev 原样返回空。改成 1 和 42，只走一轮，输出 42。如果写成 3 和 1 2，数字不够，stderr 是 Expected 3 integers after the count.，退出码 1。

想亲眼看到环：把 reverse_list 换成上面的递归版，再删掉 head->next = nullptr; 那一行，输出的最后会出现 ...(cycle?)。

从 206 往外走一步

LeetCode 92 要求只反转第 left 到第 right 个节点。核心还是这四行，只是要多记两个位置：反转段前面那个节点，以及反转段原来的第一个节点（反转后它变成段尾，要接上后面剩下的部分）。先把 206 的四行写到不用想，92 就只是在两端各接一根线。

LeetCode 25 每 k 个一组反转，是把 92 重复若干次。三道题的共同点是：每一刻都要知道「谁还指着剩下的链表」。画出上面那种 done/rest 两栏，再写代码，比直接写快。

递归在链状结构上会退化成和长度一样深，这件事在排序里也出现过：快排在已排序数组上取 a[lo] 当基准，调用栈同样变成一条链，只不过那里先感觉到的是慢，这里先感觉到的是崩。

LeetCode 234（回文链表）是这四行的另一个常见用法：用快慢指针找到中点，把后半段按本文的迭代写法原地反转，再和前半段逐个比较，额外空间只有 O(1)。比较完以后把后半段再反转一次，链表就恢复原样，调用方不会察觉。凡是要求 O(1) 额外空间、又必须从尾部往回看的链表题，通常都会用到这四行。