算起来反转链表这组题我前前后后刷了三轮每次都有新的体会。最开始就是死记硬背迭代的三指针交换后来被问到递归版本当场就卡住了。再后来把206、反转前N个节点、92这三道题放在一起对比着啃才算真正把链表的指针操作给吃透。这篇文章就是想把这三道题的来龙去脉一次说清楚从迭代到递归、从反转整个链表到反转一个区间最终落到一个可以记住的统一解法。如果你刷这几道题感觉总是一看就会、一写就废那这篇应该能帮你把最后一公里的问题解决掉。1. 从一道经典题看链表反转的本质先放下代码想清楚一个问题反转链表到底在反转什么很多人第一反应是“把节点的指向反过来”这话没错但不够本质。真正翻转的是指针的关系方向。原本每个节点指向自己的后继反转之后每个节点要指向自己的前驱。链表的物理存储顺序没变变的是链接关系。这就引出一个关键认知链表操作的核心不是“移动数据”而是“修改指针”。数据待在原地动的永远是指针。1.1 链表反转题族的共同骨架206反转整个链表、反转前N个节点、92反转区间链表这三道题表面上是三道题实际上是同一道题的三种变形。它们共享同一个核心操作把一段连续的链表节点从正序链接变成逆序链接。如果把这个公共操作抽象出来就是下面的过程从头节点开始逐个取出节点让每个取出的节点指向前一个节点确认边界在哪处理好被断开的两端。唯一不同的是边界条件整个链表没有前驱和后继需要接续前N个节点需要处理好“N之后那段谁来接”的问题区间反转则同时面临着前后两端的接续。提示刷链表题最忌讳“背代码”。后面你会发现只要把边界条件搞清楚这三道题的解法几乎是同一套代码在改边界。这是我喜欢把三道题放在一起看的原因题目之间的递进关系本身就提供了最好的学习路径。1.2 为什么说迭代和递归是两种思维模式很多教程会把迭代和递归放在一起讲但一开始就对比两种写法反而容易乱。我的经验是先把迭代吃透再理解递归最后对比两者效果最好。迭代的精髓是**“带着状态往前走”**。从头到尾遍历链表每走一步当前节点的指针就被修正。这个过程里我们用若干个临时变量记住“前一个节点”“当前节点”“下一个节点”保证链不断。递归的精髓是**“从后往前修正”**。先走到链表末端然后在一层层的回归过程中修改指针方向。递归解法里最难理解的其实是“head.next.next head”这句后面我会专门拆解。一句话总结迭代麻烦在“变量管理”递归麻烦在“理解回归”。两者没有绝对优劣看场景和面试要求选择。2. 核心基础篇反转整个链表206从零到一206题是这一组题的地基。如果你连它都没吃透后面的前N个节点和区间反转都会飘。所以这一节我多花点篇幅把迭代和递归都讲透。2.1 迭代法的三指针核心逻辑迭代法的思路特别直白我要让每个节点反指那就从头开始一个一个改。需要用三个变量prev当前节点的前一个节点初始为nullcurr当前要处理的节点初始为headnextTemp保护现场用保存当前节点的下一个节点。为什么要三个指针因为单向链表只能往后走一旦改了当前节点的next指向后面的节点就“失联”了。所以需要先用nextTemp把下一个节点存下来再放心大胆地改next。看一下迭代实现的完整代码class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseList(head: ListNode) - ListNode: prev None curr head while curr is not None: nextTemp curr.next # 1. 暂存下一个节点 curr.next prev # 2. 当前节点指向前一个 prev curr # 3. prev 前进到当前 curr nextTemp # 4. curr 前进到下一个 return prev # 循环结束时 prev 就是新头用几个具体的节点走一遍逻辑。假设链表是 1 - 2 - 3 - None初始prevNone, curr1第1轮nextTemp21.nextNoneprev1curr2第2轮nextTemp32.next1prev2curr3第3轮nextTempNone3.next2prev3currNone结束prev3新链表 3 - 2 - 1 - None。这就是迭代的全部过程。核心就一句话每轮循环干三件事暂存后继、反转指针、双指针前进。2.2 递归法的“假设子问题已解决”迭代好理解但很多面试官会追问“你能用递归写吗”这时候你再写不出来印象分会打折扣。递归的核心思路是**“把大问题拆成小问题假设小问题已经解决”**。对于反转链表来说可以这样思考如果我已经把 head.next 之后的链表反转成功了那我只需要把 head 接到这个已反转链表的尾部整个链表就反转完成了。关键问题来了怎么把 head 接到尾部答案是head.next.next head。这句话是递归版里最劝退的一句我拆开讲。在递归栈“归”的过程中head 是当前层的节点head.next 是已经被反转好的那段的“尾节点”。原本 head.next 指向的是反转后子链表的尾部。要让 head 成为新的尾部就要让原来的尾部指向 head也就是让 head.next 的下一个指向 head。同时必须断掉 head 原本指向 head.next 的链接否则链表会成环。def reverseListRecursive(head: ListNode) - ListNode: if head is None or head.next is None: return head newHead reverseListRecursive(head.next) head.next.next head # 让后一个节点指回当前节点 head.next None # 断开当前节点向后的链接 return newHead递归的执行过程可以跟着一个 1 - 2 - 3 的链表走一遍reverseListRecursive(1)调用reverseListRecursive(2)reverseListRecursive(2)调用reverseListRecursive(3)3.next为None直接返回3回到2这一层head2, head.next3执行3.next22.nextNone返回3回到1这一层head1, head.next2执行2.next11.nextNone返回3。最终得到 3 - 2 - 1 - None。返回的newHead一直是原始链表的尾节点 3。注意递归最后一定要把head.next置为None否则原来的头节点会残留指向第二个节点的链接链表会出现环遍历时会死循环。这是写递归版最容易忽略的细节。2.3 为什么要同时掌握两种写法很多刷题的人会问既然迭代能解为什么要学递归第一面试会问。这类题目简单但经典面试官常用来考察基础能力递归作为对比方案出现频率极高。第二递归版是解决更复杂的链表反转问题的阶梯。后面的反转前N个节点和区间反转用迭代写其实也不难但递归写法在边界处理上更有“模式感”一旦形成套路反而不容易错。第三递归思想本身是算法面试的高频考点链表反转是练递归思想的极佳载体——代码短、逻辑清晰、拆解自然。我的建议是迭代作为主力解法递归作为必会解法两个都要能默写。3. 进阶变体反转前 N 个节点后的边界对比反转整个链表会了咱们加一个限制条件只反转前 N 个节点后面的保持原样。这个变体题目本身不一定直接出现在面试里但它是通向92题的中点站建议别跳过。3.1 与 206 题的唯一区别反转整个链表时head反转完需要指向None因为后面什么都没有了。反转前 N 个节点时原链表的第 N 个节点的next指向第 N1 个节点。反转后第 N1 个节点变成了这段子链表的“后继”不能被丢掉。所以在递归过程中需要记录一个“后驱节点”successor也就是第 N1 个节点。整个递归过程在n 1时到达“最底层”此时要做的额外操作是记录successor head.next然后返回head。3.2 带后驱记录的递归模板先看代码successor None def reverseN(head: ListNode, n: int) - ListNode: global successor if n 1: # 记录第 n1 个节点 successor head.next return head # 以 head.next 为头反转前 n-1 个节点 newHead reverseN(head.next, n - 1) head.next.next head head.next successor # 不是置为 None而是指向后驱 return newHead和 206 递归版的对比差异只有两处n 1时多记录了successor head.nexthead.next的指向从None变成了successor。原因很简单整个链表反转时没有后继而前 N 个节点反转时第 N1 个节点是真实存在的反转后的原头节点必须链到它身上。我用一个具体例子走下流程。链表 1 - 2 - 3 - 4 - 5反转前 3 个节点预期 3 - 2 - 1 - 4 - 5。递归调用链reverseN(1, 3)→reverseN(2, 2)→reverseN(3, 1)最底层n1successor4返回3head2这层3.next22.nextsuccessor4返回3head1这层2.next11.nextsuccessor4返回3。最终得到 3 - 2 - 1 - 4 - 5成功。实战心得写reverseN时最容易错的是没把successor声明成全局变量或成员变量。如果把它当成普通局部变量在递归的某一层赋值后上一层读不到代码表现得很像“玄学”。刷题时建议直接用全局变量简单直接。3.3 迭代版前 N 节点反转的核心逻辑其实迭代版也完全可以解决这个变体。核心思路是把前 N 个节点当作一小段局部链表用三指针法反转同时用tailNext记住第 N1 个节点最后把反转后的尾节点接上tailNext。这部分的迭代逻辑我建议直接在下一节的区间反转中一起掌握因为区间反转的迭代实现天然包含这个逻辑。先单独理解“要接上后驱”这一点即可。4. 核心场景92 题区间反转的迭代实现重头戏来了。区间反转要求给定链表和两个整数 left、right反转从 left 到 right 这段子链表。相比前两个变体它多了“左边界”和“右边界的接续”处理。4.1 区间反转的四个关键位点反转区间链表本质上是把整条链表切分成三段第一段原链表中 left 之前的节点需要保持原序第二段从 left 到 right 的节点需要反转第三段right 之后的节点需要保持原序。反转完成后把这三段重新接起来。这需要对以下四个节点做标记preleft 前一个节点反转完成后它的next要指向新区间的头leftNode当前 left 位置的节点反转完成后它变成区间的尾需要指向第三段rightNode当前 right 位置的节点反转完成后它变成区间的新头postright 后一个节点反转后要和第二段连接。理清这四个变量代码就好写了。4.2 头插法迭代最推荐的解法92题最主流的迭代解法是“头插法”也叫穿针引线法。思路是在 left 到 right 这段区间内不断地把“下一个节点”搬到已处理区间的头部反复操作就能完成反转而不需要断开链表。具体步骤找到pre和leftNode。pre是 left 位置的前驱固定pre不动把leftNode视为当前反转区间的尾部用next指向即将处理的节点每次把next节点挪到pre之后更新leftNode.next指向next的下一个逐步完成反转。直接看代码def reverseBetween(head: ListNode, left: int, right: int) - ListNode: dummy ListNode(-1) dummy.next head pre dummy # 1. 移动 pre 到 left 前一个位置 for _ in range(left - 1): pre pre.next # 2. cur 指向 left 节点 cur pre.next # 3. 头插法执行 right - left 次 for _ in range(right - left): next_node cur.next cur.next next_node.next next_node.next pre.next pre.next next_node return dummy.next用实际例子走一遍。链表 1 - 2 - 3 - 4 - 5left2right4预期结果 1 - 4 - 3 - 2 - 5。初始化dummy - 1 - 2 - 3 - 4 - 5 - Nonepredummy。pre移动left-11次pre1cur2第1轮头插right-left2轮中的第1轮next_node cur.next也就是3cur.next next_node.next即2.next 4next_node.next pre.next即3.next 2pre.next next_node即1.next 3。此时链表1 - 3 - 2 - 4 - 5第2轮头插next_node cur.next此时cur仍是2所以next_node 4cur.next next_node.next即2.next 5next_node.next pre.next即4.next 3pre.next next_node即1.next 4。此时链表1 - 4 - 3 - 2 - 5。完成。注意cur从头到尾没有移动一直是原来的 left 节点。它被头插法操作推移到了区间的末端成为反转后区间的尾部。提示头插法会改变pre.next的指向循环次数是right - left。写得时候要时刻提醒自己cur.next这一步是在“回收下一个节点”pre.next这一步是在“把节点插入到头部之前”。顺序错了链表会被撕断。4.3 区间反转的边界情况和 dummy 节点的妙用区间反转最常见的边界问题是left 1也就是从头开始反转。此时 left 前没有节点pre无处可放。解决方案就是引入哨兵节点dummy。dummy是一个指向head的虚拟节点它本身不存任何有效数据只为了让pre有前驱可指。最后返回dummy.next即可因为无论是否从头反转dummy.next始终指向真正的头节点。这个方法非常简单实用统一处理了左边界为 1 的特殊情况而且代码不用额外分支判断。如果left1, right5就相当于反转整个链表有了 dummy直接走头插法right-left轮也能得到正确结果。所以 206 题也可以视为 92 题在某边界下的特例。4.4 递归实现区间反转的思路扩展92题的递归思路是把问题转化为“反转前 N 个节点”。怎么转化分两步如果left 1直接复用reverseN(head, right)如果left 1把头节点当作已经固定的部分对head.next递归调用reverseBetween(head.next, left-1, right-1)。递归代码如下def reverseBetweenRecursive(head: ListNode, left: int, right: int) - ListNode: if left 1: return reverseN(head, right) head.next reverseBetweenRecursive(head.next, left - 1, right - 1) return head这个解法的巧妙之处在于通过递归逐步把left减少到 1把区间反转问题转化成了已经会解的“反转前 N 个节点”问题。理解时要把握住递归的“递推关系”链表头节点不动整个问题就变成了对head.next反转从left-1到right-1的区间。每递归一层问题规模缩小一点直到left变成 1。初始head1, left2, right4时reverseBetween(1, 2, 4)left ! 1调用reverseBetween(2, 1, 3)reverseBetween(2, 1, 3)left 1调用reverseN(2, 3)返回4 - 3 - 2回到第1层head.next 4 - 3 - 2链表变为 1 - 4 - 3 - 2 - 5。这写法很漂亮代码极短但在面试中当面写容易紧张出岔。建议先把迭代稳健掌握递归作为加分项。5. 迭代 Or 递归两种方案怎么选最稳到这里两道题、三种变体的实现都过了一遍。接下来解决一个很多读者私信问的问题面试到底该写哪一种先亮我的观点刷题练习阶段两版都练面试现场默认先写迭代。原因是迭代对内存更友好空间复杂度 O(1)不容易碰栈溢出代码迭代过程直观可控现场 debug 更简单。5.1 复杂度对比维度迭代法递归法时间复杂度O(n)遍历一次O(n)递进 回归也是访问每个节点一次空间复杂度O(1)只用固定几个指针O(n)递归调用栈需要消费额外空间现场可调性变量状态直观出错容易定位回归过程不直观容易越描越乱代码简洁度稍长但结构简单很短但理解门槛高边界处理需要显式控制边界递归条件天然处理部分边界如果链表特别长比如上万节点递归版有栈溢出风险。实际面试里不一定会刻意攻击这一点但确实会有面试官用来考察你对复杂度理解得透不透。5.2 面试官更想看哪种我个人和身边做面试官的朋友交流时发现大家普遍接受两种写法但更看重两件事第一你能不能讲清楚自己的思路。比如用迭代头插法时能不能解释为什么cur一直不动用递归时能不能讲明白head.next.next head的意思。能把为什么讲清楚的候选基本都给了过。第二换一些边界条件后你的解法是否依然成立。这比背板子更能反映真实水平。比如原题考206面试官追问如果只反转中间一部分怎么办有递归基础的人会从容很多。5.3 一种提高熟练度的练习策略我自己的经验是把三道题的迭代和递归各写三遍不要一次写完就过。第一遍照着思路抄第二遍关掉参考纯手写第三遍给自己讲思路后默写。第三遍尤其重要。能“讲出来”和能“写出来”是两回事很多知识以为自己懂了一讲才发现逻辑链条中缺了一环。6. 从 206 到 92 的统一思路总结写到这里可以停下来理一理这三道题到底在考什么。表面上看是几种指针操作实质是三种问题抽象206边界为链表首尾的全局反转反转前N一边反转、一边保留“未反转部分”的局部反转92在局部反转基础上同时控制左右边界的区间反转。把这三道题放在一起理解你会得到一个统一的认知框架反转一段链表本质上就是确定“反转起点”“反转终点”“前驱”“后继”这四个位置然后在这段区间内反复执行“把下一个节点挪到头部”这个动作。6.1 从一道题迁移到另一道题的“心法”做题时可以用一个口诀帮助迁移“区间反转先找边界再想接续”。反转整个链表前后边界都是空不需要接续反转前N个节点后继要接上第 N1 个节点前驱为空反转区间前后都非空要同时处理好两个接续点。再看一眼头插法代码的骨架next_node cur.next # 取出下一个待处理的节点 cur.next next_node.next # 让当前节点跨过下一个节点直接连到下下个 next_node.next pre.next # 把取出的节点指向当前区间头 pre.next next_node # 把区间头更新为取出的节点这段四行代码是区间反转的“心脏”。理解了这四行206、92 的头插法都能写出来。面试时如果紧张忘了完整代码只要记得这四行的逻辑就能现场推演出完整的解法。6.2 以区间反转为例的实操记忆点为了帮助记忆我再从操作角度把 92 题的迭代步骤整理成四个环节定位迭代找到preleft 前一个节点初始化cur pre.next作为当前区间的第一个节点循环执行right - left次头插操作收尾返回dummy.next。这四个环节中最容易出错的是第三步的循环次数。我已经帮不少同学排查过代码发现很多人的问题不是思路不对而是循环次数写成了right - left 1。多插一次链表结构就乱了。推荐做法是拿一个小链表老老实实走一遍确认循环次数后再写上。7. 常见问题与排查技巧实录把实操中遇到的典型问题和排查思路整理一下。这些都是我实际刷题和帮别人改代码时反复遇到的坑。7.1 链表成环控制台一直刷屏最常见的情况递归反转后没有把原head.next置为None导致新链表末尾节点又指回前面的节点遍历时无限循环。排查方法反转后从头遍历看指针是否能在 N 步之内走到None。如果是递归写法重点检查head.next None或head.next successor是否执行。7.2 头插法循环次数比预期多一次症状是反转结果多翻转了一次区间后面还跟着一个被“吞掉”的节点。排查思路先打印中间状态观察每轮循环后的链表变化。重点检查for _ in range(right - left)是否被误写成range(right - left 1)。7.3 忘记处理 left 1 的边界没有dummy节点的年代最怕left1因为pre没有地方指向。到时候还要写一大堆if分支代码特别丑还容易漏。现在的统一做法dummy节点永远先新建pre从dummy开始移动。这样无论left是 1 还是大于 1代码逻辑完全一致。7.4 递归里 successor 没生效症状反转前 N 个节点时后半段明明应该保留结果被切掉了。或者输出结果后半段乱掉。原因successor在某一层赋值之后没有被上层共享。修复方法是把它定义为全局变量或者在类内定义为成员变量保证所有递归层都能正确读取。7.5 不会把递归函数转换成迭代这是读者问得最多的问题之一。这里分享一个逆向工程方法先写出正确的递归写法然后提取递归操作中的关键步骤改用显式变量记录状态。拿reverseList举例递归版的核心操作在“归”的过程中重复执行head.next.next head。如果把它改成迭代写法的视角其实就是每一步把next取出来插到前面。一旦发现两种写法在操作层面有共同点转换就变得容易。8. 拓展延伸从链表到其他数据结构链表反转这个小知识点其实有不少可延展的地方。写出来给大家一个参考方向。8.1 与 K 个一组反转链表的关联K 个一组反转链表是把区间反转推广到“多个区间”的复合场景。基本思路是按 K 个节点分组每组都用一次区间反转同时维护好组与组之间的接续关系。学完92题后再刷 K 个一组反转的题目思路会通得特别快。8.2 与回文链表的关联判断回文链表经典做法之一是“找到中点 反转后半段”。其中反转后半段的操作就是区间反转的变体。所以刷完这一组题回文链表题也会顺手很多。8.3 从链表到数组逆序的思维迁移链表和数组的逆序操作在实际工程中经常成对出现。数组的原地反转利用首尾双指针交换链表则靠指针操作。两者在思维上可以类比都是在保持存储不变的情况下修改“访问顺序”。9. 以面试者的角度做一份自测清单输出这篇长文后我担心有人看完又陷入“好像都懂了”的错觉。每天都有无数人在评论区说“谢谢作者学到了”但真到了白板上手写时还是卡壳。所以最后给一份自测清单你能完整回答这些问题才算真的过关。9.1 迭代自测题不借助任何参考写出 206 题迭代版要求 60 秒内完成解释为什么需要nextTemp这个临时变量写出 92 题迭代版并用 1 - 2 - 3 - 4 - 5left2, right4 手动推演完整流程回答头插法里cur为什么不需要移动回答循环次数为什么是right - left而不是right - left 19.2 递归自测题不借助任何参考写出 206 题递归版用自己的话解释head.next.next head是什么意思写出反转前 N 个节点的递归版并说明successor的作用把 92 题通过递归转化成“反转前 N 个节点”问题写出完整代码。如果以上题目你都能不看任何提示答出来那这一组题的掌握程度已经超过很多面试候选人了。如果还有卡壳的地方建议回到对应章节再看一遍然后用“讲给自己听”的方式复述一遍。刷题最后拼的不是手速是对题目的理解深度。链表的题尤其如此——数据结构的操作就那几招关键是你能不能把问题抽象成那几个招数能解决的形态。祝刷题顺利。