反转链表LeetCode 206：三指针迭代与递归详解

反转链表，LeetCode 206，大概是算法题海里最被人低估的一道题。做了这么多年面试官，我和同事私下核对过很多次：能把这道题写出两种解法的人，链表基本不会再出大问题；写不出来的，后续环节十有八九也吃力。它不像KMP那样要背next数组，不像动态规划那样需要设计状态转移，题面简洁到只有四个字——反转链表。可就是这四字，每年能刷掉一大片候选人。

这道题要解决的实际问题相当直观：给你一个单链表 1->2->3->4->5，反转后变成 5->4->3->2->1。看起来简单，但它几乎是链表类题目的地基，后面要遇到的区间反转、K个一组反转、回文链表判断，全部建立在今天这套解法上。无论你是正在准备大厂算法面试，还是刚学完指针或引用想找点手感，又或是工作里偶尔需要手写链表的工程师，这篇文章都值得看完。

1. 反转链表到底在考什么

1.1 题面就一句话，核心是“改指针方向”

先给题面：给定单链表的头节点 head，反转链表并返回新链表的头节点。单链表的节点结构通常长这样：

struct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} };

如果是 Python，就是：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

单链表的物理结构决定了：节点在内存里并不连续，每个节点只保存一个 next 指针。所以“反转”从来不是把 val 倒序输出，而是把每个节点的 next 指针全部掉头：原本指向后一个节点，现在指向前一个节点；原来的头变成尾，原来的尾变成头。

很多人第一次写时会用最朴素的做法：把链表遍历一遍放进数组，再倒序重建。这个做法完全正确，复杂度也说得过去，时间 O(n)、空间 O(n)，但面试官想看到的是“能不能只改指针、不额外申请节点就完成”。这正是反转链表成为基础题的原因：它逼你直接面对指针移动顺序这个问题。

我平时带人，会先让他画三个框：pre、cur、nxt。画完之后再动手写代码，思路会清楚很多。这也是为什么我在下文会反复强调画图这件事。

1.2 为什么说它是算法面试的必考题

在算法面试题里，大家讨论最多的往往是 KMP、贪心、DP、归并排序这些“大套路”，但真实面试环节中，反转链表出现的频率比它们高得多。原因很直接：它代码量短，一屏能放下；它陷阱多，空指针、断链、死循环都可以藏在一两行里；它还适合追问，把迭代版写完后，面试官一定会问“能不能递归？空间复杂度多少？如果只反转中间一段怎么改？”

这些问题从易到难，刚好能把候选人的掌握程度摸得很清楚。我作为面试官，看候选人写这道题时，重点从来不是他最后是否编译通过，而是他写代码时的停顿和习惯。一眼就能看出是真的理解链表，还是在背题。

所以这道题值得你在任何数据结构教材里都作为“第一个必须手写熟练的链表算法”来对待。后面的 LRU 缓存、排序链表、树与链表转换，很多都绕不开对基础指针操作的自如运用。

2. 迭代法：三指针的完整推演

2.1 核心口诀：先存后指再移动

迭代解法有三个指针：pre 指向已反转区间的头部，也就是当前节点的前驱；cur 指向当前待处理的节点；nxt 临时保存 cur 原本的后继。整个循环就做三件事：先存 nxt，再把 cur 的 next 指到 pre，然后 pre 和 cur 一起后移。我习惯把这三步缩成六个字：先存、后指、再移动。

为什么必须“先存”？因为第二步会直接改写 cur->next，一旦改写完成，原来的后继就再也找不到了。拿开车变道打比方：先看一眼后视镜确认后面没情况，再打方向盘；你要是先打方向盘再回头，事故就来了。代码里同样道理，顺序错了整个链表就被截断。

我用一个长度为 4 的链表推演给你看。初始时 pre = null，cur = 1，链表是 1->2->3->4->null。

第一轮：nxt = 2，1->next = null，pre = 1，cur = 2。此时 1 已经变成新链表的尾部。 第二轮：nxt = 3，2->next = 1，pre = 2，cur = 3。此时 2->1 已经连上。 第三轮：nxt = 4，3->next = 2，pre = 3，cur = 4。 第四轮：nxt = null，4->next = 3，pre = 4，cur = null。

循环结束，pre = 4，就是新链表的头。这个过程不需要背，只要每一步都问自己“这一轮之后，pre 和 cur 分别在哪”，就能推出来。强烈建议你拿一张纸自己走一遍。

2.2 循环结束条件与代码落地

循环条件应该写成 while (cur != null)，而不是 while (cur->next != null)。原因很简单：最后一个节点也必须被反转，它的 next 要指向倒数第二个节点。如果循环在 cur->next == null 时提前退出，最后一个节点会被留在原地，整条链表从中间断开，输出永远是错的结果。

完整的 C++ 实现：

ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nxt = cur->next; cur->next = pre; pre = cur; cur = nxt; } return pre; }

Python 版本只是换了个皮：

def reverseList(head): pre = None cur = head while cur: nxt = cur.next cur.next = pre pre = cur cur = nxt return pre

这里有一个特别容易忽略的细节：返回值是 pre，不是 head。循环结束后，head 指向的节点已经在最末尾，它的 next 被置成 null，它已经不是链表头了。如果你返回 head，拿到的就是一个“孤独的尾节点”，后面什么都没了。第一次写的人很容易在这里栽一下，我见得太多了。

提示：迭代版的额外空间只有三个指针，是 O(1)；时间上每个节点恰好处理一次，是 O(n)。

3. 递归法：从“信任递归”开始

3.1 递归到底做了什么

递归版的核心思想是：先让当前节点后面的整段链表反转好，再回来处理当前节点。你可以理解成从后往前反转，但更准确地说，是递归深入到末尾，再逐层回溯执行指针调整。

先看代码：

ListNode* reverseList(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode* newHead = reverseList(head->next); head->next->next = head; head->next = nullptr; return newHead; }

递归的入口是 reverseList(head->next)，你不需要在脑子里把每一层都展开，只需要相信一件事：这个函数会把以 head->next 开头的这一段链表完整反转，并把新头返回出来。这是递归的“信任模型”，和数学归纳法是一回事：先假设 n-1 规模的问题已经解决，只处理当前这一步。

以 1->2->3->4->null 为例。调用 reverseList(1) 后，它先去调用 reverseList(2)，reverseList(2) 又去调用 reverseList(3)，一直递归到 reverseList(4)。4 的 next 是 null，直接返回 4。回到 reverseList(3)，此时新头是 4，3 的 next 是 4，执行 3->next->next = 3，也就是让 4->next = 3，再执行 3->next = null。此时链表变成了 4->3。再往上回溯，2 接上 3，1 接上 2，最终得到 4->3->2->1。

需要特别注意的细节是，子递归返回后，head->next 这个节点虽然已经被反转进新链表，但它原本和 head 断开过一次，因为子递归里把它自己当成了新的 head，同样执行了最后的 head->next = null。所以回溯到当前层时，一定要主动重新建立“下一个节点指回当前节点”的关系，也就是 head->next->next = head。这就是那两行看似魔法的代码存在的意义。

提示：递归返回后，newHead 是整个反转后链表的新头，它在子递归里已经完整成形；当前层要做的只是把当前节点挂到它的末尾。

3.2 为什么递归版不是尾递归

迭代版的额外空间是 O(1)，递归版是 O(n)。原因是递归过程中每一层调用都会在调用栈里压一个栈帧，当前层在递归返回后还要继续执行，所以必须保留变量和返回地址。对一个 n 很大的链表，比如 10 万个节点，部分语言里递归会直接栈溢出。C++ 默认栈空间一般也就几 MB，十万层深度的递归非常危险。

还有一个容易搞混的点：这个递归不是尾递归。尾递归要求递归调用是函数的最后一个动作，但这里 reverseList(head->next) 返回之后，还要执行 head->next->next = head 和 head->next = nullptr 这两行，当前层不能提前退场。编译器即使开了优化，也没法把它优化成循环。

那什么时候用递归？面试里，递归版更多是为了展示你理解“分治”和“信任模型”，或者作为迭代法之外的第二个解法。真实工程代码里，除非你能确定链表长度很小，否则我更推荐迭代版。这不是递归不行，而是工程上要尽量避开不可控的栈深度风险。

4. 三个高频变体：区间反转、K个一组、回文判断

4.1 区间反转：虚拟头节点拯救特判

加上区间限制后，题面变成：给定 left 和 right，只反转第 left 到第 right 之间的节点。难点在于，如果 left 等于 1，链表的头就会变，原地处理需要一大堆 if 特判。

先说解决方案：加一个虚拟头节点 dummy，让它指向真正的 head。这样哪怕反转的是从头开始的区间，真正的头节点也不是“反转操作的受害者”了，所有操作都规整到“某个 pre 的 next 链”里。dummy 这个技巧几乎是所有链表边界题的万金油，值得刻进肌肉记忆。区间反转可以用头插法，每轮把 cur 的下一个节点 nxt 摘出来，插入到 pre 后面。移动 right-left 次之后，区间就已经反转完成。核心代码：

ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode* dummy = new ListNode(0); dummy->next = head; ListNode* pre = dummy; for (int i = 0; i < left - 1; ++i) pre = pre->next; ListNode* cur = pre->next; for (int i = 0; i < right - left; ++i) { ListNode* nxt = cur->next; cur->next = nxt->next; nxt->next = pre->next; pre->next = nxt; } return dummy->next; }

这个写法第一次看会觉得绕：为什么是 nxt->next = pre->next 而不是先把 pre->next 改了？因为必须先把 nxt 从原来的位置摘干净，再把它插到头部位置。如果你先改 pre->next，原链表后面的顺序还没固定住，整条链表可能就断了。建议你照代码走一遍 1->2->3->4->5、left=2、right=4，看一遍就明白。

提示：区间反转可以用“先局部反转再拼接”的方法，也可以用头插法。头插法看起来巧妙，但本质还是“每次把下一个节点搬到最前面”，和整链反转的指针保存逻辑完全一致。

4.2 K个一组反转：先数长度再动手

LeetCode 25 的题面是：每 K 个节点一组反转，最后一组如果不足 K 个，保持原顺序。这题是区间反转的进阶版。基本做法是：从前往后遍历，每一组反转前先数一下剩余长度，如果不够 K 个就停止；如果够 K 个，就反转这一组的内部顺序，然后把上一组的尾节点接到本组的新头上。

关键在组与组之间的衔接。反转前需要记录两个节点：这一组的头（反转后会变成尾）和这一组的前驱 preGroup。反转结束后，上一组尾的 next 要指向这一组的新头，这一组的新尾的 next 要指向下一组的起点。如果你直接用 reverseBetween 那种 pre 指针，反转完一组后 pre 也要跟着一起迁到这一组的尾部，否则第二组的 pre 位置就错了。

我的建议是，先实现一个“给定 start 和 length，反转 length 个节点并返回新头”的小函数，再组合使用。每一步只处理一小块逻辑，比一个巨大循环里同时维护四五个指针要容易 debug 得多。

4.3 回文链表判断：快慢指针加反转

回文链表题目说白了就是：判断一个链表是否对称。直观做法是遍历两次，第一次把节点值放进数组，第二次用双指针比较，时间 O(n)、空间 O(n)。面试官看到这种答案通常会追问：能不能把空间压到 O(1)？

这时反转链表就派上用场了。第一步，用快慢指针找中点，慢指针一次走一步，快指针一次走两步。第二步，把中点之后的半段链表反转。第三步，从头指针和中点之后的指针同时出发，逐个比较 val，如果全程相等就是回文。整个过程只用了三个指针和常数个临时变量，额外空间确实做到了 O(1)。

这里有个细节：链表长度为偶数时，中点有两个候选位置，快慢指针停在哪需要按你的习惯统一，否则后半段的边界容易多一个或少一个节点。我的习惯是快指针走完后，慢指针停留在前半段的末尾，反转后半段时从 slow->next 开始。写完用 1->2->2->1 和 1->2->3->2->1 两个用例各跑一遍，基本不会错。

两两交换节点也是同样的思路，只是每组的 K 等于 2。能熟练写区间反转的人，两两交换就是送分题。

5. 面试追问环节：O、Ω、Θ怎么答

5.1 反转链表的最优复杂度

很多朋友背下了“时间 O(n)，空间 O(1)”就以为完事了，结果被面试官追问“这个 O 到底什么意思？能不能说 Θ(n)？”就会卡壳。这里把三个记号一次说清。

• O(f(n))：渐近上界，表示算法时间不会超过某个常数倍的 f(n)。工程里说 O(n)，就是在说“它大概随 n 线性增长，不会更差”。
• Ω(f(n))：渐近下界，表示算法时间至少是某个常数倍的 f(n)。证明“不可能更快”时常用，比如比较排序的下界是 Ω(n log n)。
• Θ(f(n))：紧确界，表示上界和下界同时成立，算法时间正好是 f(n) 这个量级，既不会更快到另一个量级，也不会更慢到另一个量级。

反转链表迭代版处理 n 个节点时，循环恰好执行 n 次，和链表内容无关。所以它既是 O(n)，也是 Ω(n)，合起来就是 Θ(n)。面试时说“时间 O(n)、额外空间 O(1)”完全安全；如果面试官追问“能不能说 Θ(n)”，你能说出上面这段，印象分会明显不一样。

这个知识点也正好回答了一个常见疑问：什么时候用 O、什么时候用 Θ？答案是，当你只想表达“不会比某个上界更差”时用 O；当你确认算法时间正好处于某个量级、上下都被夹住时用 Θ。工程讨论里大家习惯用 O，但理论证明里 Θ 更严谨。

5.2 空间复杂度陷阱：递归不是O(1)

接着上面说空间。迭代版只有 pre、cur、nxt 三个变量，是常数个临时空间，和链表长度无关，所以额外空间 O(1)。递归版每一层调用都要压栈，n 个节点对应 n 层递归，额外空间 O(n)。这两个结论必须分开记。

我面试时经常看到候选人写出递归版后脱口而出“空间O(1)”，这个错误很致命，因为它暴露了两点：一是对递归调用栈没有概念，二是对“额外空间”的定义不清晰。额外空间指的是除了输入结构外，程序运行时另外申请的内存，递归栈帧就是实实在在的额外内存，不能因为它是编译器自动管理的就假装不存在。

如果你在面试里被问到“递归能不能优化”，可以这样答：“可以改成迭代，空间变成 O(1)，但代码可读性会略差；在链表长度不确定的情况下，我倾向迭代版。”这个回答既懂原理又务实，印象分很高。

6. 现场写代码最常踩的七个坑

6.1 没保存后继节点：断链的头号原因

迭代版最经典的错误长这样：

cur->next = pre; pre = cur; cur = cur->next; // 错！此时 cur->next 已经是 pre，原后继丢了

第二行执行完，cur 的原后继就彻底丢了。所以正确的第三行必须先用临时变量 nxt 保存，这就是“先存”的意义。我实测过不少候选人，很多人卡住后改来改去，最终都会回到这个“保存后继”的点，说明它不是小细节，而是这道题的第一原则。

还有一个等价的错误变体：用 while (cur->next != null) 当循环条件，这样确实能保留 cur->next 用于移动，但会导致最后一个节点不进入循环，最终结果少反转一个节点。判断循环结束该看 cur 本身，不是 cur->next。

6.2 循环条件写错：最后一个节点被漏掉

上面提过，这里单独拎出来强调。正确条件是“当前节点不为 null”，而不是“当前节点还有下一个节点”。假设链表只有 1->2 两个节点：

• 条件 while (cur->next != null)：第一轮处理 1，第二轮 cur 变成 2，2->next 是 null，循环结束，2 没被处理。输出是 1，错。
• 条件 while (cur != null)：第一轮处理 1，第二轮处理 2，循环结束。输出 2->1，对。

这个坑在工程代码里尤其隐蔽，因为大多数测试链表都有多个节点，漏掉最后一个节点时输出看起来只是短了一截，如果测试用例恰好只检查头节点值，还可能被误判为正确。所以写完后一定要用至少两个节点、最好四个节点的用例自测。

6.3 测试用例清单与调试技巧

我在实际写这个算法时有个固定测试清单，整理给你：

调试时不要只依赖断点逐行走，建议在循环里打印一行：

pre=null cur=1 nxt=2 pre=1 cur=2 nxt=3 pre=2 cur=3 nxt=4 pre=3 cur=4 nxt=null

打印完和手推结果逐行对照，一行不对就说明移动顺序出错。这个“打印三指针”的方法比任何 IDE 断点都直观，因为链表结构是抽象的，你看内存地址看不出前后关系，但看 pre/cur/nxt 的变化序列一眼就知道哪一步错了。

还有一个经验：不要对着代码脑补“我应该没写错”，直接跑一个四个节点的用例，把返回值打印出来。很多次 debug 半小时，最后发现就是没有保存 nxt 或者返回了 head。前五分钟把这两个点检查完，能省下后面所有时间。

7. 反转的思想不止于链表

7.1 反转与栈：顺序问题的同构

反转在本质上就是“把先出现的变成后出现的、把后出现的变成先出现的”，这和栈的后进先出完全同构。如果你想用栈实现反转链表，流程也现成：遍历链表把节点 push 进栈，再 pop 出来重建 next 关系。这样做空间是 O(n)，不如迭代，但思路很自然。

更重要的是，这种“顺序反弹”的直觉可以用在很多地方。字符串反转、双指针头尾交换，其实就是链表反转的孪生兄弟；括号匹配、表达式求值这些经典栈应用，底层逻辑同样是在处理顺序倒过来的问题。把反转链表学透，不只是记住一个函数，而是理解了“顺序可以靠指针或栈强行扭转”这件事。

7.2 改指针方向：树旋转与图反向边

链表反转的“改指针方向”思想，在更复杂的数据结构里也反复出现。平衡二叉树旋转，本质上是重新调整几条父子指针的指向，让树重新平衡；有向图构造反向边，要遍历每条边并交换起终点，也是一次“所有指针掉头”的操作。如果连单链表的三指针都写不顺，看红黑树旋转或邻接表反向建图时会更晕。

在实际工程里，原地反转一个链表最常见的场景是逆序输出。假设一个单向链表保存了按时间追加的事件日志，现在要倒序展示，最简单的方法不是重建数组，而是原地反转一次，遍历完再反转回来。时间上 O(n) 跑两遍，但胜在省空间，逻辑也清楚。基础算法在业务里的价值往往就是这样，不炫技，但够用。

最后再分享一个我练这道题的方法。我每次面试结束，不管候选人有没有写出来，都会自己在本子上把迭代版默写一遍，然后画一遍三指针走势。坚持一段时间后会发现，所有需要改 next 指针的题，我都不会再犯“没保存后继”这种低级错误。如果你想快速把这题变成肌肉记忆，建议合上答案，先在纸上写迭代版，写完再写递归版，最后再用区间反转、K个一组反转、回文链表三个变体题练手感。这个过程重复十次，比你刷二十道新题都有用。面试时听到“反转链表”，先开口说“我准备用三指针，prev、curr、next，每次把 curr 的 next 指向 prev，再整体后移，最后返回 prev”，这个开场白本身就能让面试官放心一半。