反转链表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, val0, nextNone): 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 nullcur 1链表是 1-2-3-4-null。第一轮nxt 21-next nullpre 1cur 2。此时 1 已经变成新链表的尾部。 第二轮nxt 32-next 1pre 2cur 3。此时 2-1 已经连上。 第三轮nxt 43-next 2pre 3cur 4。 第四轮nxt null4-next 3pre 4cur 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)此时新头是 43 的 next 是 4执行 3-next-next 3也就是让 4-next 3再执行 3-next null。此时链表变成了 4-3。再往上回溯2 接上 31 接上 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、left2、right4看一遍就明白。提示区间反转可以用“先局部反转再拼接”的方法也可以用头插法。头插法看起来巧妙但本质还是“每次把下一个节点搬到最前面”和整链反转的指针保存逻辑完全一致。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 变成 22-next 是 null循环结束2 没被处理。输出是 1错。条件 while (cur ! null)第一轮处理 1第二轮处理 2循环结束。输出 2-1对。这个坑在工程代码里尤其隐蔽因为大多数测试链表都有多个节点漏掉最后一个节点时输出看起来只是短了一截如果测试用例恰好只检查头节点值还可能被误判为正确。所以写完后一定要用至少两个节点、最好四个节点的用例自测。6.3 测试用例清单与调试技巧我在实际写这个算法时有个固定测试清单整理给你用例输入期望输出说明空链表nullnull最容易崩的场景单节点11边界必须成立双节点1-22-1检查最后一个节点是否被处理奇数长1-2-33-2-1常规用例偶数长1-2-3-44-3-2-1检查中间切换点调试时不要只依赖断点逐行走建议在循环里打印一行prenull cur1 nxt2 pre1 cur2 nxt3 pre2 cur3 nxt4 pre3 cur4 nxtnull打印完和手推结果逐行对照一行不对就说明移动顺序出错。这个“打印三指针”的方法比任何 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”这个开场白本身就能让面试官放心一半。