第一次在面试现场被问“反转链表”的时候我愣住了。不是这道题不会而是“觉得自己会”和“把代码一次写对”之间差了很远。我当时拿了一个栈把所有节点存进去再一个个弹出来重建链表面试官盯着屏幕上多出来的 O(n) 空间轻轻问了一句“能不能不用额外空间把它反过来”也就是这一句让我把 LeetCode 206 从头重新刷了一遍。后来我发现这道被评为“简单”的题目坑一点不比难题少而且几乎所有链表面试都会从它或它的变形开始。今天我会把 206 反转链表彻底拆开迭代法、递归法、栈解法各有什么适用场景各自的代码怎么写边界条件哪些容易踩以及它和 92、25、234 这些高频题之间是怎么一步步串起来的。如果你正在刷 LeetCode 热门 100 题或者准备手写代码面试这篇可以当作链表的入门检查单来用。1. 一道带“简单”标签的题面试官到底在考察什么1.1 考点不是“会不会调 API”是“对 next 关系的把控”数组反转简单因为数组可以用下标随机访问arr[i]和arr[j]交换一下即可链表反转麻烦因为在单链表里每个节点只保存了指向下一个节点的指针next你无法回头访问前一个节点。要让整个链表反向本质不是“交换两个节点的值”而是“把每个节点的 next 指针从指向后一个改成指向前一个”同时还要保证所有节点不能丢反转之后头尾要正确整条链不能断。这三点听起来平淡实际动手就很容易翻车。因为在用迭代法操作时只要你先把curr.next改了当前节点后面的节点就“失联”了除非你在改之前先把后面那个节点保存下来。很多第一次写的人在纸上画一画就明白但一旦真到写代码就会栽在顺序上。这里有必要先记住最核心的三行逻辑准备一个prev指针初始为None。准备一个curr指针初始为head。每次循环先保存curr.next再把curr.next指向prev接着把prev移动到curr、curr移动到保存的下一个节点。这是 LeetCode 206 迭代解法最核心的指针移动节奏。它同时也是一种通用模板后面做反转链表 II92 题、K 个一组翻转链表25 题都会反复用到。所以我说 206 值得“背”但背的应该是这套指针移动的节奏而不是死记返回值。1.2 面试官追问“还有别的做法吗”时别只会说递归很多人在题解区看到迭代解法和递归解法觉得记住其中一个就够了。真实面试中面试官常常会追问“能不能换一种思路”“递归怎么写”“如果链表非常长递归会有什么问题”目的不是难为你而是想看你对“链表结构”和“函数调用栈”这两件事的理解深度。迭代法不需要额外空间时间复杂度 O(n)空间复杂度 O(1)适合生产代码也是我推荐你最先掌握的写法。递归法代码更短在有些语言里读起来非常优雅但它会消耗系统栈极端情况下链表长度上万就可能栈溢出。栈解法把节点全部缓存下来再重建思路最直观但额外空间 O(n)在面试里通常不是最优解。这三种方法的关系不是“哪个更好”而是“在不同限制条件下怎么选”。我建议你把三种都写一遍写完之后你会对链表的指针改向产生肌肉记忆这比刷十道重复的链表题更管用。1.3 借助 206 建立“链表题最小检查清单”我自己刷题时习惯把每类题总结成一个检查清单。对于链表面试我至少会问自己几个问题链表为空返回什么链表只有一个节点代码能不能直接覆盖反转后原来的头节点是不是变成了尾节点它的next是不是已经变成了None如果题目要求“原地修改”我有没有新建节点、使用额外数组或栈函数返回的是新链表的头节点还是原来的头节点带着这份清单做 206并逐步验证比无脑提交十次受用得多。代码能不能过是一回事你能不能讲清楚每个边界分支为什么这样处理才是面试官最终打分的依据。2. 迭代法三个指针从头到尾把 next 方向掰过来2.1 初始状态与循环不变量迭代法的循环不变量可以定义为在每一轮循环开始时prev指向已经反转好的那段链表的头curr指向还没有反转的那段链表的头。当curr走到None时说明整条链表都反转完了此时prev就是新链表的头。以1 - 2 - 3 - None为例轮次操作前 prev操作前 curr操作前 next_node操作后的连接关系1None12None - 12 - 3 - None2123None - 1 - 23 - None323NoneNone - 1 - 2 - 3结束3None无返回 prev即节点 3这段我建议你自己在纸上画一遍画完再写代码速度会快很多。很多人觉得链表题“想不明白”其实不是抽象能力差而是太少在纸上画图了。画三轮之后你会自然理解为什么先保存next_node这一步不能省。2.2 Python 实现这里是最经典的写法class Solution: def reverseList(self, head: ListNode) - ListNode: prev None curr head while curr is not None: next_node curr.next # 先保存后面的节点 curr.next prev # 反转当前节点的指针 prev curr # prev 前进一步 curr next_node # curr 前进一步 return prev我特别想提醒 Python 新手一点不要盲目用prev, curr, curr.next curr, curr.next, prev这种多重赋值来“简化”。Python 的多重赋值是先把右边表达式全部求值再依次赋值所以等号右边的curr.next取的是原始的下一个节点但同一个语句中左侧有三个赋值目标一旦某个目标对象的属性发生更新后续赋值会基于同一个新元组逻辑上不会立刻出错可这种写法的可读性很差面试时很容易把自己绕晕。我见过不少人面试时为了炫技写多重赋值结果在“curr.next到底引用哪个对象”上卡壳。老老实实用临时变量反而最稳。2.3 Java 实现Java 里没有 Python 那种多重赋值的迷惑性逻辑会更直白一些class Solution { public ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode nextNode curr.next; curr.next prev; prev curr; curr nextNode; } return prev; } }不管是哪种语言循环体里的顺序都不要随便调换。我见过最常见的错误是先写curr.next prev再写nextNode curr.next这时候nextNode拿到的其实是已经指向prev的老节点链表后半段直接丢了。调试结果就是反转后的链表只保留了 1 个节点或 2 个节点其余节点全部失联。2.4 为什么这里通常不引入哑节点dummy node反转单链表的场景中有一个问题经常被提起能不能用哑节点做头插法来解决哑节点常见于“删除倒数第 N 个节点”这类题因为需要统一处理头节点被删除的情况。但在 206 里反转前后的头节点变化是明确的旧头变新尾旧尾变新头。直接用prev和curr移动指针不需要额外占一个 dummy 节点。如果非要用头插法新建一个 dummy 节点遍历原链表每拿到一个节点就把它插到 dummy 后面遍历完返回dummy.next同样可以得到反转结果。这个做法完全可以通过提交逻辑也好理解但它本质上是在“重建”一条新链表而不是对原链表做原地反转。面试时如果被问到空间复杂度它依然只用了 O(1) 辅助空间不算错只是思路没有三指针那么纯。我自己在面试里会优先讲三指针版本因为它的思路更贴近链表底层的操作逻辑。3. 递归解法让函数调用栈替我们记住下一个节点3.1 递归是怎么把“大问题”变“小问题”的递归解法的核心思想是反转一条以head为头的链表可以先反转以head.next为头的子链表得到子链表的新头new_head然后把head.next的next指向head再让head.next指向None。用一句话概括别管整条链表怎么反转先假设“后面的部分已经反转好了”当前节点只需要接在后面即可。递归终止条件是if not head or not head.next: return head。链表为空或只有一个节点时反转结果就是它自己。class Solution: def reverseList(self, head: ListNode) - ListNode: if head is None or head.next is None: return head new_head self.reverseList(head.next) head.next.next head head.next None return new_headhead.next.next head这行是绝大多数初学者的噩梦。理解它的关键是要意识到此时head.next已经不是原来的“下一个节点”了它是反转后子链表的“尾节点”。把尾节点的next指向head就能把当前节点接到整条反转链表的尾部。3.2 用 1 - 2 - 3 - None 拆开递归过程看一个具体例子。调用reverseList(1)发现head1的next是 2不满足终止条件进入递归。调用reverseList(2)head2的next是 3继续递归。调用reverseList(3)head3的next是None满足终止条件返回节点 3。回到reverseList(2)new_head 3。执行head.next.next head即3.next指向 2此时链表是1 - 2 - 3但 2.next 还是 3。执行head.next None即2.next指向None完成子链表反转1 - 2 - 3。返回new_head 3。回到reverseList(1)new_head 3。执行head.next.next head即2.next指向 1得到1 - 2 - 3。执行head.next None断开原来的1 - 2连接。返回new_head 3。整个过程中真正干活的只有两行代码head.next.next head和head.next None。递归调用本身只是负责把问题规模缩小并且利用调用栈保存每一层“还没处理完的节点”返回时从后往前依次处理。3.3 递归在面试中应该怎么答才加分如果面试官让你写递归我建议你按下面这个顺序讲能很自然地展示思路先明确递归的终止条件空链表或只剩一个节点。再说清楚每层递归要做什么“现在我调用函数去反转剩余部分拿到剩余部分的新头。当前节点要做的是把自己接到剩余部分反转后的尾部。”最后说返回值是什么每次递归返回的都是反转后整条链的新头。要注意的是递归的空间复杂度是 O(n)。虽然 LeetCode 的测试用例一般不会让你栈溢出但生产环境里如果链表很长递归方案并不是第一选择。我在面试中通常会先给迭代法然后补一句“如果我被明确要求用递归实现我可以改成递归但要注意它要消耗 O(n) 的调用栈空间”这句话能体现工程意识容易拿到加分。4. 栈解法用起来爽但里面藏着几个大坑4.1 为什么很多刷题新手首选栈人的第一直觉是“反转就要往后看”。链表只能往后走那先把所有节点记下来再倒着串一遍的确最符合直觉。于是不少新手一上来就会写一个基于栈或数组的版本遍历链表把每个节点压栈然后依次弹栈把弹出的节点依次连接成新链表。class Solution: def reverseList(self, head: ListNode) - ListNode: stack [] cur head while cur: stack.append(cur) cur cur.next if not stack: return None new_head stack.pop() cur new_head while stack: node stack.pop() cur.next node cur node cur.next None return new_head这个版本能够 AC逻辑也清晰。如果面试官没有明确要求“原地修改”或“空间复杂度 O(1)”它并不是错误答案。但你要清楚用了栈以后总空间开销是 O(n)对于 206 这道题来说完全有更优的原地方案所以面试中它整体处于“能给分但不出彩”的位置。4.2 最容易犯的“环”错误用栈解法时有一个非常隐蔽的坑弹栈重建链表时最后一定要把新尾节点的next置为None。为什么因为原链表中节点之间的next还保留着旧方向。比如链表1 - 2 - 3 - None压栈时节点 1 的next仍然指向 2、节点 2 的next仍然指向 3。把节点 1 弹出来当新链表头再让节点 1 指向节点 2这时候1 - 2原本的next关系已经存在所以如果不小心没处理最后的next链表中就可能出现1 - 2 - 1 - 2的回环。我第一次用栈解这道题的时候就因为这个原因在本地调试了很久明明栈弹出的顺序是对的打印链表却死循环。后来才意识到旧链表的方向没有清干净。这也是为什么我不太建议新手在面试中用栈法——你可以用栈但最后一定要记得补一句“最后把尾节点的next指向None避免形成环”。4.3 栈解法什么时候反而是合适的虽然 206 用栈不是最优解但并不是说“栈解法一无是处”。如果题目要求“不改变原链表结构只返回反转后的结果”或者输入是一个值列表、而不是真正的单向链表那么用临时数组或者栈来反转完全是合理的。甚至在剖析很多双向链表、LRU 缓存之外的问题时栈也是一种常用辅助结构。所以我的建议是这道题你至少要知道栈解法长什么样但面试答题顺序要按“迭代法 → 递归法 → 其它思路”来安排。先给出最优解再展示思路广度才是面试官想看到的节奏。5. 边界条件与本地调试刷题到底怎么才能不靠运气5.1 空链表、单节点、双节点、长链表很多人在 LeetCode 上提交 206第一次就能 AC因为测试用例不算刁钻。但真正到了面试白板或者换到别的链表题边界条件没过就会很尴尬。对于反转链表我建议至少准备这几类测试用例head None直接返回None迭代和递归都要能处理。只有一个节点返回该节点本身。两个节点1 - 2反转后是2 - 1这时候最容易出现指针指错。多个节点且带有重复值比如1 - 2 - 2 - 3确保值的重复不会影响指针逻辑。大链表例如 1 万个节点验证递归解法会不会爆栈也可以顺便感受迭代解法的稳定性。5.2 在本地写个辅助函数验证LeetCode 的链表输入是数组但真正提交前本地最好有一个构建链表和打印链表的辅助函数。我每次做链表题都会先复制这样一小段代码class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_linked_list(arr): dummy ListNode() cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next def print_linked_list(head): res [] cur head while cur: res.append(str(cur.val)) cur cur.next print( - .join(res))这样你可以直接构造[1,2,3,4,5]调用reverseList(build_linked_list([1,2,3,4,5]))再用print_linked_list看输出是不是5 - 4 - 3 - 2 - 1。本地跑通之后再贴到 LeetCode心理压力会小很多。5.3 迭代法中常见的“断链”现象怎么快速定位假如你在本地测试反转1 - 2 - 3输出变成了1或者2 - 1而不是3 - 2 - 1大概率是下面两类问题在更新curr.next之前没有保存下一步节点循环进行到第二次时curr已经回到已经反转的节点链表就断了。最后返回了curr而不是prev。因为循环退出时curr是Noneprev才是新的头。有个土办法在循环里打印每一步的prev.val和curr.val。while curr: next_node curr.next curr.next prev print(fprev{prev.val if prev else None}, curr{curr.val}, next{next_node.val if next_node else None}) prev curr curr next_node观察打印结果如果第二轮next就已经是None说明你取下一个节点时取晚了。把打印删掉再提交即可。5.4 提交时注意 LeetCode 给出的链表定义不同语言的定义不同比如 Python 是class ListNodeJava 里是public class ListNode。提交前先看一眼编辑器里是否已经帮你定义了节点类如果自己重复定义会导致编译错误。这是非常基础但非常多人犯的问题尤其从本地粘贴代码过去的时候。6. 从 206 出发把高频链表题的模板顺手拿下6.1 92 反转链表 II限定区间的反转反转链表 II 要求只反转 m 到 n 之间的节点其它保持不动。解法思路是利用 206 的三指针模板找到目标区间的前一个节点固定不动对区间内部的子链表执行一次性反转。这道题是 206 最直接的变形也是我在面试中最常遇到的下一个追问方向。掌握了 206再去写 92重点就变成“定位”和“重接边界”而不是重新想怎么反转。6.2 25 K 个一组翻转链表分组反转与不足 K 个的处理25 题要求每 K 个节点一组翻转不足 K 个的保持原序。它本质上是“多次执行 206 的局部反转”同时要处理每组反转后新尾和新头之间的连接关系以及最后一组不反转的边界判断。这道题的代码量通常会到 50 行以上面试时一般不会作为第一题出现通常是在你熟练之后口述思路。但如果你能把 206 的模板写得很顺25 的核心难点就从“指针如何反转”变成了“边界如何衔接”。6.3 234 回文链表与 143 重排链表反转的经典组合用法回文链表判断常规做法是快慢指针找中点然后把后半段反转最后再和前半段对比。这里“反转后半段”就是 206 的直接应用。重排链表L0 - Ln - L1 - Ln-1 - L2 - ...也是类似套路找到中点反转后半段再交替合并两个链表。这类题目经常出现在 LeetCode 热门 100 题里而它们的共同前置技能就是 206 的不变式把一段链表的next方向整体倒过来。我把这几道题放在一起讲是想强调一个观点链表题不是靠题海战术堆出来的而是靠把少数几个基础操作练到条件反射。206 就是你练“原地反转”这个条件反射的最好载体。6.4 结合刷题热度的节奏建议从近期的刷题趋势来看LeetCode 热门 100 题、简单题题解、周赛题库讨论都把链表作为重点复习模块。周赛里如果出现链表题大概率会混合“反转 快慢指针 合并”等复合操作。我个人建议的节奏是先花一个晚上把 206 的迭代法和递归法都写熟各写 5 遍以上。再做 92 反转链表 II体会“局部反转”和“边界重连”。再做 25 题强化“分组处理”和“剩余不足一组”的判断。最后做 234 和 143这时候你会发现它们就是“快慢指针 206”的组合。等到你的手指已经能条件反射地把prev、curr、next_node排好顺序链表面试的基础题对你来说就真的不再是问题。这个状态不需要刷 100 道链表题但一定需要你在 206 上多花时间把它拆透、写透、讲透。我个人到后来面试别人时也很喜欢用 206 开头因为听候选人讲三分钟就能判断出他对链表是“真懂”还是“背题”。如果你能把边界条件主动说出来顺便补一句递归空间复杂度的取舍这一关基本就稳了。读到这里建议你关掉网页打开编辑器亲自写一遍这三种解法再回头对照题解收获会比直接抄答案大得多。
