链表反转这个题目只要刷过力扣的人十有八九都练过。我见过不少同学206题反转整个链表背得滚瓜烂熟代码写得飞快可一旦遇到92题这种反转链表某个区间的变形就开始卡壳。今天这篇笔记我想沿着反转整个链表 - 反转前N个节点 - 反转链表中的某一段II这条递进路线把迭代和递归两种主流解法完整拆开讲一遍。先说我为什么觉得这条路线很重要206题是基础它教你怎么把整条链表反过来。但实际面试里这道题很少单独出现更多是以变体的形式出现——比如反转前K个节点或者反转从left到right的区间。如果你只背了206的答案不知道它背后的指针交换原理遇到92题就会两眼一抹黑。反过来如果你把206吃透了再把反转前N个这个中间形态搞明白92题几乎就是白送的分。这篇文章适合刚接触链表的同学也适合刷过题但总是记不住细节的选手。建议边读边自己在本子上画链表结构。我的经验是链表题画图比背代码高效十倍这真不是鸡汤。1. 先啃206题三指针迭代反转整个链表206题要求把一条单向链表原地反转返回新链表的头节点。它看起来是入门级题目但里面藏着一个贯穿所有链表反转题的核心操作怎么安全地修改节点的next指针。1.1 三指针的核心next指针必须在改写前保存迭代版本的核心思想是从头到尾遍历每个节点把每个节点的next指针指向它的前一个节点。这样原来的头变成了新的尾原来的尾变成了新的头。实现上需要三个指针prev上一个已经处理好的节点初始为Nonecurr当前正在处理的节点初始为headnext_node保存curr原本的下一个节点为什么要单独的next_node因为单向链表每个节点只有一个next指针一旦执行curr.next prev它原本的下一条连接就断了。如果不提前把后面那段保存下来后面的链表就永远找不回来了。这算是链表反转里最经典的错误几乎每个初学者都会踩一次。def reverseList(head): 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 # 此时 prev 是原链表尾也是新链表头拿1 - 2 - 3 - 4 - 5 走一遍过程初始prev Nonecurr 1第1轮保存 next_node 21.next Noneprev 1curr 2第2轮保存 next_node 32.next 1prev 2curr 3第3轮保存 next_node 43.next 2prev 3curr 4第4轮保存 next_node 54.next 3prev 4curr 5第5轮保存 next_node None5.next 4prev 5curr None循环结束返回prev得到 5 - 4 - 3 - 2 - 1。提示很多新手会在循环体里写 curr.next prev; prev curr; curr curr.next。这个写法非常危险因为curr.next已经被改成了prev再用curr.next前进就会让指针往回走造成死循环或错误结果。必须用提前保存好的next_node来移动curr。这个版本的时间复杂度是O(N)因为每个节点只遍历一次空间复杂度O(1)因为只用了常数个额外变量。它的本质是原地头插法每轮都把当前节点从原链表头部摘下来放到新链表的最前端只是复用了节点对象没有新建内存。我当年学这段代码时是硬背下来的结果过了两天就忘了。后来自己花了半天画了5轮指针变化图彻底看懂之后就再也没写错过。所以真心建议你也动手画一遍尤其是摘节点、接节点、移指针这三个动作。1.2 递归思路先走到链表尾再逐层回头改指向迭代是从前往后处理递归正好反过来先把链表一路走到头再在回溯归的过程中改变指针方向。思路可以这样描述假设递归函数已经能把head.next后面的整条链表反转好并且返回了新的头节点new_head那么只需要把head这个节点接到反转后链表的尾部由于head在原链表中指向head.next而head.next在递归反转后变成了反转链表的末尾节点所以直接让head.next.next head再把head.next置为None就完成了拼接base case是链表为空或只有一个节点直接返回head。def reverseList_recursive(head): if head is None or head.next is None: return head new_head reverseList_recursive(head.next) head.next.next head head.next None return new_head用1 - 2 - 3 - 4 - 5模拟调用过程reverseList_recursive(1) 会先调用 reverseList_recursive(2)reverseList_recursive(2) 会先调用 reverseList_recursive(3)reverseList_recursive(3) 会先调用 reverseList_recursive(4)reverseList_recursive(4) 会先调用 reverseList_recursive(5)5.next 是 None返回 5回到 reverseList_recursive(4)head 是 4执行 5.next 44.next None返回 5回到 reverseList_recursive(3)执行 4.next 33.next None返回 5回到 reverseList_recursive(2)执行 3.next 22.next None返回 5回到 reverseList_recursive(1)执行 2.next 11.next None返回 5这里的递就是一直往链表深处走走到底部触发base case归就是逐层往回处理每一层解决一个节点的指向。很多同学觉得递归难是因为不知道每层递归return的是什么。记住每一层返回的都是同一个new_head也就是新链表的头这个值从base case一路向上传递。递归版的好处是代码短、逻辑集中但它有硬伤链表有多长递归调用栈就有多深。在真实项目中如果链表长度达到几万甚至更多递归很容易撑爆调用栈。所以我平时写demo或讲思路会用递归但遇到生产级代码一律迭代。1.3 迭代与递归的第一次碰面先提前说一下两者的本质区别迭代的思考单元是当前节点怎么处理递归的思考单元是当前问题怎么拆成更小的问题。206题用迭代你时刻盯着三指针怎么移动用递归你想的是后面那段链表已经反转好了我该如何把当前节点接上去。这两种思维没有绝对对错但解决不同问题时的效率完全不同。等我们看92题时你会发现递归的缩小范围思路反而比迭代更直观。第4节我会专门展开对比这里先建立一个概念就好。2. 中间桥梁反转前N个节点一次到位206题反转整条链表时最后会把head.next置为None。因为原始链表的头反转后成了新链表的尾尾节点的next必须是None。但如果我们只反转前N个节点反转完之后原链表的第N个节点变成了反转区间的头原链表的头变成了反转区间的尾。这个尾节点后面必须接上原链表的第N1个节点。这就是反转前N个节点和反转整个链表之间唯一的关键差异。很多人会在这里漏一步反转完之后忘了让原head指向第N1个节点。结果前半段是反过来了后半段整个丢了。2.1 为什么要单独学反转前N个节点92题要反转链表中从left到right的一段。如果left刚好是1问题就退化成反转链表的前right个节点。这个中间形态正是从206过渡到92的关键桥梁。力扣没有单独收录反转前N个节点这道题但它以各种变体大量出现在面试和后续题目中。我一般会建议把所有刷链表的同学把reverseFirstN当成一道独立题来练因为一旦掌握它92题就只剩下两件小事移动到left前一个节点以及反转后把端点接回去。2.2 迭代版复用206的三指针循环N次迭代版只需要把206的while循环改成固定循环N次并在循环结束后补一步连接操作def reverseFirstN(head, n): if n 1 or not head: return head prev None curr head nxt None for _ in range(n): nxt curr.next curr.next prev prev curr curr nxt # 关键连接原 head 现在指向反转部分的末尾 head.next curr # curr 是第 n1 个节点 return prev # prev 是第 n 个节点也是新链表的头用 1 - 2 - 3 - 4 - 5反转前3个来走一遍循环3轮结束后prev 3curr 4此时 1.next None2.next 13.next 2第4个节点4和第5个节点5此时还保持原样4.next 5执行 head.next curr也就是把1.next指向4最终得到 3 - 2 - 1 - 4 - 5返回prev即3这里的n不仅可以小于链表长度也可以等于链表长度。当n等于链表长度时第n1个节点就是Nonehead.next None就和206完全一致了。所以可以把206看作reverseFirstN的特例。注意n 1时要特判。n1意味着只反转一个节点反转区间里只有一个元素循环体直接执行会访问curr.next虽然也能跑但语义上没必要增加特殊情况判断可以让代码更稳。2.3 递归版用一个额外变量保存第N1个节点递归版比迭代版绕一些因为递归从头部一路深入时无法事先知道第N1个节点是谁。解决办法是在递归到底时用一个字段比如successor保存第N1个节点然后在归的过程中把头节点接上去。思路拆开看如果n 1当前节点就是第n个节点它下一个节点就是我们要找的successor保存下来返回当前节点作为新链表的头如果n 1递归反转当前节点后面的前n-1个节点递归返回后执行 head.next.next head把当前节点挂到已反转子链表的尾部再执行 head.next successor让当前节点指向后驱节点最后返回递归得到的new_headsuccessor None # 保存第n个节点的后一个节点 def reverseFirstN_recursive(head, n): global successor if n 1: successor head.next return head new_head reverseFirstN_recursive(head.next, n - 1) head.next.next head head.next successor return new_head注意这里head.next successor而不是像206递归版那样置为None。因为206反转的是整条链表链表本来就到头了而反转前N个时head要接到第N1个节点上。如果不把successor挂上去后半段链表就丢了。以反转前3个为例调用过程reverseFirstN_recursive(1, 3)递归调用 reverseFirstN_recursive(2, 2)reverseFirstN_recursive(2, 2)递归调用 reverseFirstN_recursive(3, 1)reverseFirstN_recursive(3, 1)n 1successor 4返回节点3回到 reverseFirstN_recursive(2, 2)2.next.next 2即3.next 22.next successor(4)返回3回到 reverseFirstN_recursive(1, 3)1.next.next 1即2.next 11.next successor(4)返回3最终得到 3 - 2 - 1 - 4 - 5。提示上面的代码为了简洁用了global。实际在类的成员函数里建议用一个实例属性self.successor或者用嵌套函数配合nonlocal避免全局变量污染。这个小细节在写正式代码时很常见虽然面试题里一般不深究但养成好习惯总没坏处。3. 正餐力扣92题反转链表II92题的原意是给你单链表的头节点head以及两个整数left和right1-indexed反转从位置left到位置right的链表节点返回新的头节点。比如 1 - 2 - 3 - 4 - 5left2right4输出 1 - 4 - 3 - 2 - 5。3.1 题目拆解定位边界、反转子链表、重新拼接我把这个题拆成三步找到left前一个节点pre反转从pre.next开始的right - left 1个节点把反转后的头尾接回原链表第2步本质上就是2.2节的reverseFirstN只是一般不是从链表头开始而是从pre.next开始。reverseFirstN函数里的head就是子链表的头反转后它变成子链表的尾它的next自然指向右边界之后的节点这部分逻辑天然成立。所以核心工作其实集中在定位pre这一步。定位成功之后后面的反转和拼接只是把reverseFirstN的输入参数改了。3.2 虚拟头节点处理left1的边界神器如果left1那么pre应该是左边界之前的节点可链表头没有前驱节点。如果不做处理直接就让pre head代码会崩。常见解法是创建一个虚拟头节点dummy令dummy.next head。这样一来无论left等于几pre都能通过移动指针找到因为dummy永远可以作为起点。这个dummy节点相当于哨兵它本身不参与业务逻辑只是为了统一处理边界。很多新手觉得dummy多余但在头节点也可能被反转的题目里dummy是保住结果头节点的关键哪怕反转后的头不是原来的head我们最后也只要返回dummy.next就行。3.3 迭代解法先定位再反转最后接回拼接法代码def reverseBetween(head, left, right): if head is None or left right: return head dummy ListNode(-1) dummy.next head pre dummy # 1. 定位到 left 前一个节点 for _ in range(left - 1): pre pre.next # 2. 反转区间从 pre.next 开始反转 right-left1 个节点 start pre.next # 反转子链表的头 prev None curr start nxt None for _ in range(right - left 1): nxt curr.next curr.next prev prev curr curr nxt # 3. 拼接回原链表 start.next curr # 反转后 start 变成末尾指向右边界之后 pre.next prev # pre 指向反转后的新头 return dummy.next再来看看另一种更加常见的头插法。它的思路是在区间内遍历每个节点把当前节点的下一个节点不断插到pre后面从而逐步完成倒序。这个方法不需要记录start代码更紧凑。def reverseBetween(head, left, right): if head is None or left right: return head dummy ListNode(-1) dummy.next head pre dummy for _ in range(left - 1): pre pre.next curr pre.next # 第一个要处理的节点 nxt curr.next # 它原本的下一个节点 for _ in range(right - left): # 把 nxt 从当前位置摘下来头插到 pre 后面 curr.next nxt.next nxt.next pre.next pre.next nxt nxt curr.next return dummy.next解释一下循环里三条语句的用意curr.next nxt.next跳过nxt让curr直接指向nxt的后继。这一步把nxt从原链表中摘了出来nxt.next pre.next让nxt指向当前已反转区间的新头部也就是把nxt放到最前面pre.next nxt更新pre的next为nxtnxt成为新的区间头最后 nxt curr.next重新取下一个要摘的节点还是用 1 - 2 - 3 - 4 - 5left2right4 走一遍。pre指向1curr指向2。初始pre.next 2curr 2nxt 3第1轮2.next 43.next 2pre.next 3nxt 4 当前子链表3 - 2后面4 - 5仍挂着第2轮2.next 54.next 3pre.next 4nxt 5 当前子链表4 - 3 - 2结尾接5循环结束得到 1 - 4 - 3 - 2 - 5头插法的好处是代码简洁不需要单独处理start但理解门槛略高。如果第一次见我强烈建议你手动画一遍别光盯着代码看。我在面试别人时发现能清晰讲出头插法的人对链表指针的理解通常都很扎实。3.4 递归解法利用left1直接套用reverseFirstN递归版本能把代码写得非常短。核心逻辑是如果left 1问题退化为反转从当前头节点开始的前right个节点直接调用reverseFirstN_recursive(head, right)如果left 1把大问题缩小为先递归处理head.next中的子区间[left-1, right-1]处理完后再把head放到子链表头部def reverseBetween_recursive(head, left, right): if head is None: return head if left 1: return reverseFirstN_recursive(head, right) head.next reverseBetween_recursive(head.next, left - 1, right - 1) return head还是用 1 - 2 - 3 - 4 - 5left2right4 来走调用 reverseBetween_recursive(1, 2, 4)left不为1先递归调用 reverseBetween_recursive(2, 1, 3)reverseBetween_recursive(2, 1, 3) 命中left1等价于 reverseFirstN_recursive(2, 3)把 2 - 3 - 4 反转为 4 - 3 - 2并且2.next接上successor即5返回4回到第一层此时head是1执行1.next 4返回1整条链表变成 1 - 4 - 3 - 2 - 5递归实现的空间复杂度是O(N)因为调用栈深度和链表长度相关。它的优势是代码极短而且和reverseFirstN的衔接很自然。如果面试中你能秒写这个版本会加分不少但前提是你能讲清楚为什么递归调用后参数要各减1。4. 迭代Or递归面试时该怎么选这个问题我在面试别人和模拟面试的场合被反复问到几乎每次讨论链表反转都会延伸到究竟用迭代还是递归。这里从几个维度说起。4.1 空间复杂度是硬门槛迭代解法在原地修改指针只用了常数级额外空间O(1)。递归解法每一层递归都要占用栈帧空间复杂度是O(N)。极端情况下比如链表特别长递归会直接栈溢出。我曾在某个后台服务的线上问题排查里遇到过类似情况一个模块用递归处理超长链表结构数据量一上来进程就崩改成循环实现后内存占用直接降了一个数量级。虽然面试题很少真的给出超长链表但空间复杂度这个点你一定要能清晰地答出来。4.2 思维模型是真正的分水岭迭代的核心是状态转移你盯着当前节点思考它如何变化然后让三个指针按既定顺序前进循环结束条件就是边界。这种思维方式贴近计算机底层——CPU本质上就是在做一连串当前状态 - 下一个状态的变换。递归的核心是子问题分解你不需要关心整条链怎么转你只负责回答如果后面一段已经反转好了我当前这个节点应该怎么连。92题的递归解法里你甚至不需要亲自动手反转中间那一大段只要把区间不断缩小到left1剩下的交给reverseFirstN。我的个人体验是人对子问题分解往往更容易理解但对底层的调用栈开销往往没有直觉。所以很多人觉得递归好懂、难调而迭代是难想、好调。这也是我建议初学链表时先吃透迭代再用递归顺手验证逻辑的原因。4.3 把选择标准变成面试话术如果面试官问你为什么不用递归或者迭代和递归怎么选可以这样组织回答如果链表长度未知或可能很长优先迭代。理由很直接空间O(1)、不会栈溢出如果只是讲解思路可以先讲递归因为代码更短、更贴合问题的递归结构但说完之后主动补充不过递归空间复杂度是O(N)链表很长时我会改用迭代如果面试官追问还能写一种解法吗那正好把两种都呈现出来这套话术的核心不是证明某个方法天下第一而是体现你知道权衡。能主动说出迭代省空间、递归更直观、但有栈溢出风险这句话已经超过不少候选人了。4.4 用一道扩展题检验掌握程度最后出一道扩展题就当作自测写一个函数反转链表的前k个节点然后接上原链表剩余部分k可能小于链表长度也可能等于链表长度。如果你能在5分钟内分别写出迭代和递归版本说明你已经完成了从206到92的思维升级。这个5分钟检验法是我自己用来评估面试准备程度的方法。做不到也不用急把上面的代码多抄几遍、多画几轮图过一个月再回来做你会发现顺畅得多。5. 常见Bug与调试心得速查这一节我把自己踩过的坑整理出来同时附上排查思路希望能帮你少走弯路。5.1 最经典的指针丢失典型错误curr.next prev prev curr curr curr.next # 错误curr.next 已经被改写正确做法是提前保存next_node然后让curr next_node。排查思路很简单一旦发现结果链表在某个位置断开或者出现奇怪的循环优先怀疑某个节点的next在保存之前被修改了。5.2 边界条件left1、right链表长度、只有两个节点left1必须用dummy否则反转后无法确定新头位置right是链表末尾反转完start.next应指向None此时curr刚好是None逻辑天然成立不需要特判leftright区间只有一个节点反转没有意义很多实现会让区间长度变成0从而出错直接特判返回head节点数只有1个206迭代版没问题递归版靠base case处理强烈建议准备一个只有2个节点的测试用例手动跑一遍所有边界情况。别小看这种简单样例它能排查掉一半以上的隐藏bug。5.3 调试三件套画图、打印、小样本我做链表题常用的调试流程是纸上画链表从头到尾每轮循环用不同颜色的笔标出执行前后的指针变化写一个打印函数把链表每个节点值依次打出来每次关键操作前后调一次先用小样本测试比如head 1-2-3、left1、right2确认逻辑后再测复杂样本这套流程看似简单但很多人刷题时直接大脑模拟宁可凭想象也不动手画图。结果就是代码看着没问题一跑就崩。工具就在手边多画几笔不丢人。5.4 常见问题速查表症状可能原因怎么修反转后链表断了后半段丢失反转区间结束后没有把 start.next 指向右边界之后循环结束后执行 start.next curr返回的头节点不对left1 时没有用 dummy加上 dummy最后返回 dummy.next递归版出现奇怪环反转后没有把某节点 next 置为 None 或 successor206递归里必须 head.next NonereverseFirstN递归里必须 head.next successor进入死循环指针移动时用了被修改的 curr.next提前保存 next_node移动时用保存值区间反转后原有顺序错乱反转长度写错拼接法用了 range(right-left)拼接法循环 right-left1 次头插法循环 right-left 次最后再分享一个我个人的习惯遇到任何链表反转类的问题先问自己三个问题——从哪里开始转转多少个转完之后和谁接把这三个答案想清楚代码怎么写基本就迎刃而解了。回头再看看206、reverseFirstN和92这三道题你会发现它们只是这三个问号的答案在层层递进而已。