反转链表 II 详解：虚拟头节点与迭代递归全解-北京尧图网络

如果你拿着“Leetcode 103 反转链表 II”这个标题去翻常见题库大概率会愣一下不少刷题平台里“反转链表 II”的标准题号是 92而 103 通常对应的是另一道二叉树题。但这不影响今天的核心你手里的这份资料只是把题目顺序重新编排了要解的还是同一个经典问题——给定一个单链表再给两个位置 left 和 right只把区间内的节点顺序反转区间外面的部分保持原样。这道题我愿称之为链表操作里的分水岭。能把它写清楚的人说明对节点的 next 引用已经形成了条件反射写不清楚的人多半还在靠背代码硬撑。我见过不少学习者全链表反转背得很熟一到“只反转中间一段”就懵原因不是笨而是没有理解局部反转需要的四个关键位置。今天就把这条链路完整拆开从迭代到递归从易错点到测试用例一次性讲透。1. 先厘清题目反转局部链表和反转整个链表差在哪1.1 全链表反转的固定套路反转整个链表是很多人的入门代码逻辑也很简单def reverse_list(head): prev None cur head while cur: nxt cur.next cur.next prev prev cur cur nxt return prev核心操作就三步先存下当前节点的下一个节点 nxt再把当前节点的 next 指向前一个节点 prev最后整体右移。这套逻辑能解决“从头到尾”的反转因为它不需要在意头节点的位置变化——反正最后返回的必然是原来的尾节点。但局部反转不一样。你只知道 left 和 right不知道这段区间在整个链表中的位置也不知道区间前一个节点和后一个节点是谁。如果还傻乎乎地从头开始反转很容易把链表前半段搞乱。1.2 局部反转真正难在哪局部反转的难点不是反转本身而是“接回去”。反转一段区间相当于把一条完整的链条拆下来一段倒过来之后再装回原处。你至少要同时掌握四个关键位置区间前一个节点我叫它 left_prev区间第一个节点反转后会变成区间最后一个区间最后一个节点反转后会变成区间第一个区间后一个节点用来衔接后半段这就像换一根水管你得先关掉两端阀门把旧管拆下来换上新管再把两端重新拧紧。任何一个接点没对准整条线路都会漏水。对比维度全链表反转局部区间反转需要记录的位置前驱节点 prev、当前节点 cur区间左前驱、区间首节点、区间尾节点、区间后继头节点是否可能变化一定会变只有 left 1 时可能变边界接回不需要必须重新连接左前驱和区间后继常见错误丢 next 引用接回时顺序写反把这张表看清楚你就能理解为什么几乎所有标准题解都要用一个叫 dummy 的虚拟头节点。2. 虚拟头节点dummy 节点为什么能简化问题2.1 头节点参与反转时的麻烦先抛一个典型场景链表是 1→2→3→4→5命令是反转 left1 到 right3。反转后头节点会从 1 变成 3你最终返回的应该是 3而不是原链表头。如果不用虚拟头节点你就要单独写一个 if 判断头节点是否会被反转然后分别处理两种情况。代码瞬间多了很多分支逻辑也变得脆弱。dummy 节点的作用就是把这个特殊情况“抹平”。我们在真正的头节点前面再加一个节点 dummy让 dummy.next 指向 head。即使原头节点被反转走dummy.next 也会自动指向新头节点。最后统一返回 dummy.next不用再关心 left 是不是 1。2.2 四个指针各司其职以迭代解法为例我会用四个指针把区间拆得明明白白指针名指向位置职责dummy虚拟头节点统一处理头节点变化最终返回值入口pre区间左前驱每次把节点搬到它后面永不动cur区间第一个节点固定为反转区间最左侧节点thencur 的下一个节点每次被移动到 pre 后方的节点这个命名来自一种经典写法把区间右侧的节点一个一个“头插”到 pre 后面。头插法听起来抽象但实际操作很像打牌时把一张牌从牌堆中间抽出来放到最上面——反复抽反复放就完成了反转。2.3 为什么“看图能懂一写就废”很多人会有这个体验照着题解画图每一步都看得懂合上答案自己写就报错。原因在于链表节点只有一个 next 指针你每改变一次 next就可能让之前保存的引用失效。打个比方你手里拿着一张写着“下一站地址”的字条按字条走到对应地点后这张旧字条就作废了。如果不先抄下新的“下一站地址”你就会迷路。代码里那句nxt cur.next就是在“抄地址”必须先做再做别的操作。理解了这一点后面那些看似枯燥的指针交换其实都只是在重复同一个动作先保存再修改最后移动。3. 迭代解法两种写法任选一种吃透3.1 头插法逐个把右侧节点拎到前面先说最经典的写法代码很短但第一次看的人容易绕进去class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def reverseBetween(head: ListNode, left: int, right: int) - ListNode: if not head or left right: return head dummy ListNode(0, head) pre dummy # 步骤一让 pre 走到区间左前驱 for _ in range(left - 1): pre pre.next # 步骤二cur 固定在区间第一个节点then 是它下一个节点 cur pre.next then cur.next # 步骤三反复把 then 移到 pre 后面 for _ in range(right - left): cur.next then.next # 绕过 then相当于先把 then 摘出来 then.next pre.next # then 的下一个指向区间当前第一个 pre.next then # 把 then 放到 pre 后面 then cur.next # 更新 then 为下一个待处理的节点 return dummy.next这段代码里最需要理解的是 for 循环的次数。区间长度是right - left 1第一个节点 cur 不需要移动剩下需要被拎到前面的节点数量就是right - left。所以循环次数正好是区间内除第一个节点之外的其他节点数量。有人会问为什么每次都是pre.next而不是用一个临时变量记录区间第一个节点这正是头插法的精髓。pre.next 在过程中会不断变化它始终指向“当前区间反转后的第一个节点”。每次把 then 挂到 pre.next 之前then 就会成为新的区间头。3.2 先切断再反转命名更直观的版本如果你觉得头插法太绕我推荐下面这种“先定位、再断开、最后接回”的写法。它每一步都做了什么事变量名直接告诉你def reverseBetween(head: ListNode, left: int, right: int) - ListNode: dummy ListNode(0, head) # 1. 找到区间左前驱 left_prev dummy for _ in range(left - 1): left_prev left_prev.next # 2. 找到区间首节点和区间尾节点 left_node left_prev.next right_node left_node for _ in range(right - left): right_node right_node.next # 3. 记录区间后继 successor right_node.next # 4. 把区间断开进行反转 prev None cur left_node while cur ! successor: nxt cur.next cur.next prev prev cur cur nxt # 5. 接回原链 left_prev.next right_node left_node.next successor return dummy.next这个版本虽然代码行数更多但结构非常清晰几乎是按“需求文档”逐条翻译的。第 4 步本质上就是把 1.1 小节里的全链表反转代码搬过来只不过反转的终点不是 None而是区间后继节点 successor。3.3 手动走一遍1→2→3→4→5left2right4我们用头插法完整跑一遍感受指针变化。初始状态dummy→1→2→3→4→5→Nonepre 先走到节点 1cur 指向节点 2then 指向节点 3。第一轮循环cur.next then.next让 2 直接指向 4此时链表变成 1→2→4→53 已经被“摘出去”了。then.next pre.next让 3 指向 2形成 3→2。pre.next then让 1 指向 3整体变成 1→3→2→4→5。then cur.nextcur 还是 2cur.next 现在是 4所以 then 更新为 4。第二轮循环cur.next then.next让 2 直接指向 5此时 4 被摘出来链表变成 1→3→2→5。then.next pre.next让 4 指向 3。pre.next then让 1 指向 4整体变成 1→4→3→2→5。then cur.nextcur 还是 2cur.next 现在是 5所以 then 更新为 5循环结束。最终结果是 1→4→3→2→5完全正确。3.4 两种写法的选择建议头插法代码短但可读性差适合已经熟练掌握链表操作的人先切断再反转的写法虽然长但变量职责单一适合初学者也适合面试时边写边讲思路。我个人更推荐第二种。原因很简单真实工作里不是每题都要用最精炼的解法而是要用最不容易出错的解法。面试官看重的是你能不能让别人听懂而不是能不能把代码压到最短。4. 递归解法从“反转前 N 个节点”扩展出来如果说迭代解法是“顺着链表走”那递归解法就是“先把大问题拆成小问题”。递归思路在面试中属于加分项理解它能让你对链表结构有更深一层的感觉。4.1 先写一个能反转前 n 个节点的函数要反转任意区间可以分两步先能反转“从头部开始的前 n 个节点”再通过递归把区间起点移到头部。反转前 n 个节点的递归写法def reverse_first_n(head, n): # 递归到第 n 个节点记录它的后继 if n 1: successor head.next return head, successor new_head, successor reverse_first_n(head.next, n - 1) head.next.next head head.next successor return new_head, successor这里有个关键点当 n 1 时我们返回的 head 是第 n 个节点同时把它的原本下一个节点记录下来记为 successor。整个递归回溯过程中successor 一路传回来最终让反转后的尾部接回后半段。如果你在纸上画一下 1→2→3→4→5 的反转前 3 个节点过程会发现递归到最底层时head 是节点 3此时记录 successor 为节点 4回到上层后节点 2 的 next 指回节点 1节点 1 的 next 接上节点 4。结果是 3→2→1→4→5。4.2 用递归处理任意区间有了reverse_first_n任意区间就很好办了。如果 left 恰好是 1那问题直接变成“反转前 right 个节点”。如果 left 不是 1就把 head 向后挪一位同时 left 和 right 各减一变成子问题def reverse_between_recursive(head, left, right): if left 1: new_head, _ reverse_first_n(head, right) return new_head head.next reverse_between_recursive(head.next, left - 1, right - 1) return head这个思路非常干净每一次递归都在说“把起点往后挪一个节点同时区间长度缩短一位”。递归到 left 1 时当前 head 就是区间原来的第一个节点剩下要做的就是反转前 right 个节点。注意right 也在同步减。因为在递归子问题里区间右端点的位置也整体左移了一位。这里如果只减 left 不减 right反转范围就会偏大属于高频错误点。4.3 递归方案的成本递归解法的时间复杂度同样是 O(n)空间复杂度是 O(n)因为它需要 n 层递归栈。面试中如果要求空间 O(1)迭代解法还是首选。不过递归解法的价值在于思路迁移比如“二叉树里反转部分路径”“反转双向链表的部分区间”等场景都更容易从递归框架出发。5. 边界情况与易错点现场写代码最容易翻车的地方5.1 left1头节点被反转这是最经典的坑。如果不用 dummy 节点当 left 1 时左前驱节点不存在整个逻辑会崩。所以无论用哪种迭代写法dummy 节点都是必需品。我已经数不清见过多少次这样的报错明明反转结果是对的返回的却是原来的头节点结果前半段完全乱掉。只要统一返回 dummy.next就不会有这个问题。5.2 leftright区间长度为 1如果 left 等于 right区间内只有一个节点反转前后没有任何变化。代码里直接加一个if left right: return head既能节省时间也避免后续空指针风险。还有一种更隐蔽的情况left 和 right 相邻比如 left2right3。此时只循环一次需要确保两节点交换后左右两侧的连接都正确。用头插法跑一遍会发现它天然支持相邻节点交换不需要额外特判。5.3 引用更新顺序写错很多人的代码看上去很接近正确但结果却是错的问题往往出在这两行then.next pre.next pre.next then有人会先写pre.next then再写then.next pre.next。这会导致 then 的 next 指向它自己形成环。原因很简单pre.next then已经把 pre 的指向改了你再读 pre.next 拿到的就是 then 自己。一句话总结先把 then.next 接到正确位置再移动 pre.next顺序不能反。5.4 对 None 取 next在切断再反转的写法中while cur ! successor这个条件非常安全因为 successor 是区间右端点的下一个节点cur 走到 successor 就停止不会出现对 None 取 next 的问题。但如果你把循环条件写成while cur and cur ! successor或者while cur.next在某些区间到达链表尾部的情况里就可能越界。我的建议是继承这个写法不要自己加多余的条件。5.5 别被节点的值欺骗还有一个小坑反转链表操作的是节点指针不是交换节点的值。虽然很多测试用例里节点值不重复但链表可能包含相同数值的节点。千万不要试图通过值匹配来定位节点一定要基于“第几个位置”来移动指针。6. 测试用例、复杂度分析与变体延伸6.1 我常用的手写测试用例每次写完反转链表的代码我会习惯性跑一遍下面这些用例缺一不可输入链表leftright期望输出空链表 None11None[1]11[1][1,2]12[2,1][1,2,3,4,5]24[1,4,3,2,5][1,2,3,4,5]15[5,4,3,2,1][1,2,3]12[2,1,3][1,2,3]22[1,2,3]你可以发现覆盖了空链表、单节点、全反转、部分反转、头节点反转、区间长度为 1 这些情况后代码基本就稳了。面试时我会先在白板上写这些用例再动手写代码这样思路更清晰。6.2 时间和空间复杂度迭代解法的时间复杂度是 O(n)因为需要遍历链表定位 left即使区间很短定位也要走完 left 之前的节点。空间复杂度是 O(1)只用了几个指针变量。递归解法时间同样是 O(n)但空间复杂度是 O(n)递归栈深度最多接近链表长度。LeetCode 一般对这两种写法都接受工业级代码里我会更偏向迭代写法毕竟递归深度太深的链表在极端情况下可能触发栈溢出。6.3 变体延伸每 K 个一组反转掌握区间反转后可以做一道更有意思的变体给你一个链表每 K 个节点一组进行反转最后一组不足 K 个则保持原样。解题思路就是把区间反转封装成一个函数然后从头开始每次找到第 K 个节点调用区间反转接回去再跳转到下一组的左前驱。这道题的框架完全建立在今天讲的“定位左前驱反转区间接回后继”之上。所以别小看这道“反转链表 II”它其实是很多复杂链表题的底层积木。我在实际刷题中体会最深的一点是不要背代码要把链表反转理解成“先摘节点、再插节点”两个动作的组合。一开始写错很正常最有效的调试方式是每循环一次就 print 一遍链表状态看到底是哪个 next 指向了错误位置。多跑几轮之后你会发现自己对 next 引用的敏感度明显提升——这个能力在二叉树、图论和日常写业务代码处理链式结构时都非常值钱。希望这篇拆解能让你少走一点我当年走过的弯路。

反转链表 II 详解：虚拟头节点与迭代递归全解

相关推荐

用 Flutter 构建 OpenHarmony 井盖巡检地图与排班系统

生产级大模型私有化部署全链路指南：从显存规划到高可用架构

Docker部署phpipam：开源IPAM工具实现高效IP地址管理

更多资讯

数据库课程设计实战：从建库到事务闭环的完整指南

ai-agent-book：从入门到 Agent 工程实践（一）

【PMSM滤波代码2】PMSM未知负载转矩观测EKF。MATLAB例程（负载增广EKF与实际仿真结果）。订阅专栏后可查看完整代码

MySQL 8.4课程设计实战：从教科书模型到生产级数据库

解Bug之路-隔离故障点后业务不恢复?-热点Key处理与亚稳态故障

PostGIS 3.5.0 + PostgreSQL 17 Windows二进制捆绑包详解

今日更新

声子晶体仿真：三角晶格与六角晶格的能带计算实战

度假村安保定岗定编：岗位梳理、编制测算与排班设计

COMSOL等离子体模块实战：氩气双层DBD仿真建模全解析

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？