链表指定区间反转：从指针定位到头插法，彻底掌握LeetCode 92题

链表内指定区间反转是LeetCode第92题也是各大厂面试中出现频率相当高的一道基础算法题。题目本身并不难但很能拉开差距能把单链表整体反转背下来的人不少能一气呵成写对区间反转的却不多。原因在于它同时考察三件事——指针定位是否精准、局部反转是否熟练、边界处理是否敏感。这篇文章我会从题目拆解、思路推演、多语言实现、边界测试到面试追问把这道题完整讲透。适合准备算法面试的读者也适合刚学完链表、想找一道综合题练手的初学者。1. 题目拆解与核心考点1.1 题目到底在考什么题目描述很简洁给定单链表头节点head和两个整数left、right反转从位置left到位置right的链表节点返回反转后的链表。位置从 1 开始计数left和right一定满足1 left right 链表长度。这道题表面上是“反转”实际上考的是三件事。第一指针定位。你得先准确找到区间的前一个节点。很多人习惯从head开始往前走left步结果走到的是left节点本身而不是它前面的节点。这里只需要走left - 1步差的这一步就是整道题的第一个分水岭。第二局部反转。区间内的反转和整体反转逻辑上是一致的但多了“接回去”这一步。你在反转中间节点的同时要保证区间前端和区间后端不断链、不错位。第三边界处理。left 1时没有前驱right 链表长度时区间直接连到尾部这两种情况是最容易写出 bug 的。说实话这些考点每一个单独拎出来都不难但合在一起对基本功的要求就上来了。这也是为什么这道题被归入“leecode必刷基础算法题”的常客。1.2 最常见的三个误区我在帮别人 review 代码和看面经的时候见过太多人在这道题上踩坑总结下来有三个误区出现频率特别高。误区一先把整个链表反转再截取区间。这个思路听起来可行实际做起来会非常痛苦。因为整体反转之后所有节点的相对位置都变了你还得想办法找回原来的left和right位置再切出区间最后又要考虑拼接顺序。操作量翻倍出错概率成倍上升面试官也不会觉得你有巧思只会觉得你没抓住问题的本质。误区二通过交换节点值实现反转。有些人觉得反正链表里存的是整数那我把left到right之间的节点值拿出来倒序放回去不就行了这样确实能过部分测试用例但面试官考察链表题的核心目的是看你如何处理指针和引用关系而不是看你如何操作数组。如果节点里包含的不止一个值比如带随机指针的复杂链表值交换就彻底失效了。误区三循环边界用错。链表题的位置默认是 1-based 的但很多人写循环时下意识按 0-based 来定位pre的时候多走或少走一步结果整体错位。这种错误很难肉眼排查因为链表的链接关系不打印出来根本看不出来。1.3 为什么说它是“试金石”题判定一道题是不是好题要看它能不能区分出不同水平的候选者。区间反转就是这样的题。新手可能见过整体反转的写法但面对区间反转会犹豫区间外的节点怎么保住区间内的节点怎么处理老手则会在十秒内构建出“虚拟头节点 头插法”的框架。这种思维差距正是面试官想看到的。更重要的是这道题是很多复杂链表问题的基础模块。你以后会遇到的“K 个一组反转链表”“回文链表判断”“重排链表”等题目核心思想都能回溯到区间反转。把这道题练透等于给后面的进阶题打好地基。2. 思路推演把反转拆成三步2.1 区间反转的本质摘、转、接把链表想成一列火车车厢每节车厢用挂钩连接车厢只能往一个方向走。整体反转就像是把这列火车掉头而区间反转是把中间几节车厢单独摘下来、掉头、再重新挂回去。这个过程拆开就是三件事找到区间的前一个节点pre相当于找到摘钩的位置。把区间内的子链表反转相当于把摘下来的车厢掉头。把反转后的子链表接回原来的前后节点之间相当于重新挂好钩子。这里有个重要认知反转链表并不是“物理上把整段搬走再搬回来”而是通过不断改变节点的next指针指向来实现的。每次改一个指针链接关系就变化一次。区间反转只是在局部反复做这件事。所以与其说这道题考反转不如说它在考“链表插入”和“链表遍历”的组合运用。你每轮操作的本质都是把区间后面的一个节点插到pre的后面。这也是为什么有人说这道题练的是头插法。2.2 为什么必须加虚拟头节点先看一个场景left 1要从头节点开始反转。此时区间的前一个节点不存在你没法用统一的逻辑去处理“定位前驱”这一步。想绕开这个问题最优雅的做法就是加一个虚拟头节点也叫哨兵节点、dummy node。做法很简单在真正的head前面再建一个节点dummy让dummy.next head。这样无论left是几都能统一从dummy开始走left - 1步找到区间前驱。很多教材会强调“不带头结点的单链表”意思是链表本身没有额外的哨兵节点。但这和我们在解题时加一个局部虚拟头节点并不冲突——dummy只是函数内部的一个局部变量不是链表本身的一部分它存在的意义纯粹是为了统一边界逻辑、避免空指针判断。如果不用虚拟头节点也能写。你需要在left 1时单独处理把pre当作空节点代码会多几个分支看起来像是能跑但逻辑可读性差很多出 bug 的概率也更高。面试中我强烈建议直接上虚拟头节点简单、稳妥、不容易翻车。2.3 迭代法核心操作逐步拆解以1 - 2 - 3 - 4 - 5为例反转第 2 到第 4 个节点目标当然是1 - 4 - 3 - 2 - 5。先定义两个关键指针。pre指向区间前驱也就是节点1cur指向区间的第一个节点也就是节点2。注意cur在整个过程中始终指向节点2它不会变我们反复操作的是cur.next。然后进入循环循环次数是right - left次也就是 2 次。第一轮next cur.nextnext指向节点3。cur.next next.next把节点2的下一个指向节点4此时链表变成1 - 2 - 4 - 5节点3被“摘”出来了。next.next pre.next节点3的下一个指向pre现在的下一个节点此时是节点2把3挂在2前面。pre.next next让pre的下一个指向节点3链表变成1 - 3 - 2 - 4 - 5。第二轮next cur.next此时cur还是节点2cur.next已经是节点4了所以next指向节点4。cur.next next.next节点2的下一个指向节点5。next.next pre.next节点4的下一个指向节点3。pre.next next链表变成1 - 4 - 3 - 2 - 5。循环结束结果正确。为什么循环次数是right - left而不是right - left 1因为区间内有right - left 1个节点第一个节点已经在最前面了只需要把后面right - left个节点依次“摘”到区间头部。每摘一次区间头就多一个节点摘完最后一个节点就是反转完成。还有一个细节容易写错三条赋值语句的顺序。很多人会把next.next pre.next和cur.next next.next调换位置结果一跑就断链。原因是必须先断开cur和next的链接让cur提前指向next的后继节点如果先改next.nextcur.next里存的指向就丢了后面再取next.next时会取到已经被改过的指针链表就乱了。3. 代码实现C、Java、Python 对照3.1 C 语言实现不带头结点的经典解法很多嵌入式开发者和 C 语言学习者会特别强调“不带头结点的单链表”场景因为真实的低级数据结构往往就是这种形态。但解题时我们仍然可以用一个局部虚拟头节点来兜底。struct ListNode* reverseBetween(struct ListNode* head, int left, int right) { struct ListNode dummy; dummy.next head; struct ListNode* pre dummy; for (int i 1; i left; i) { pre pre-next; } struct ListNode* cur pre-next; for (int i 0; i right - left; i) { struct ListNode* next cur-next; cur-next next-next; next-next pre-next; pre-next next; } return dummy.next; }这里我用的是栈上分配的dummy变量而不是malloc。好处很明显不用手动free也不用担心内存泄漏函数结束自动失效。如果你用了malloc一定要在返回前free掉否则面试官可能会追问内存管理问题。C 语言版本最容易错的点有两个。一个是返回值一定要返回dummy.next因为当left 1时原来的head已经不是新链表的头节点了。另一个是pre的定位循环从 1 到left - 1不是 0 到left - 1也不是 1 到left。3.2 Java 实现虚拟头节点简化边界Java 的写法和 C 语言几乎一模一样区别只是语法和对象引用的处理方式。class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode pre dummy; for (int i 1; i left; i) { pre pre.next; } ListNode cur pre.next; for (int i 0; i right - left; i) { ListNode next cur.next; cur.next next.next; next.next pre.next; pre.next next; } return dummy.next; } }Java 里的ListNode是一个引用类型赋值操作传递的是引用本质上和 C 的指针操作是一回事。唯一的区别是dummy new ListNode(0)在堆上创建对象不需要手动释放垃圾回收器会处理。我在写 Java 版本时有一个习惯给虚拟头节点的值随便赋个 0因为反正不会用到。但要注意如果你打印链表调试dummy的值会显示出来别被它误导了误以为是链表的一部分。3.3 Python 实现引用操作与易错点Python 的链表题写起来最接近伪代码逻辑也最清晰。class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(0, head) pre dummy for _ in range(left - 1): pre pre.next cur pre.next for _ in range(right - left): nxt cur.next cur.next nxt.next nxt.next pre.next pre.next nxt return dummy.nextPython 没有指针概念但每个变量名都是对对象的引用pre.next next本质上是在修改对象属性。这个模式下变量名就格外重要。我把临时节点命名为nxt就是为了避免和内置的next()函数混淆也让自己在头脑中明确“这是当前节点的后继”这个语义。Python 版本常见的坑是把for _ in range(left - 1)写成range(left)或者把range(right - left)写成range(right - left 1)。我建议你把示例用例代入走一遍逐轮打印出cur.val和nxt.val很快就能发现边界错在哪。3.4 三个版本实现对比对比维度C 语言JavaPython虚拟头节点栈上结构体变量堆上对象前端带参构造内存回收手动最好不用 malloc垃圾回收垃圾回收核心循环完全一致完全一致完全一致易错点指针运算与整体考虑引用赋值变量命名与边界三个版本的核心逻辑完全一致都是一套“先定位前驱再头插法逐轮反转”的流程。语言差异只影响语法写法不影响算法思想。所以我一直建议学这道题时不要局限于某一种语言先用最熟悉的语言把逻辑跑通再对照翻译成其他语言这样理解最深刻。4. 边界测试与排查实录4.1 边界条件与测试用例设计面试写代码一定要主动构造边界用例这能体现你的细致程度。我建议至少跑下面这几个用例用例说明期望输出[]空链表[][1]left1, right1单节点[1][1,2,3]left1, right1区间只有一个节点[1,2,3][1,2,3,4,5]left2, right4常规区间反转[1,4,3,2,5][1,2,3,4,5]left1, right5整体反转退化为区间[5,4,3,2,1]用[1,2,3,4,5]、left2、right4这个用例你可以把每一步的链表状态打印出来初始1 - 2 - 3 - 4 - 5第一轮后1 - 3 - 2 - 4 - 5第二轮后1 - 4 - 3 - 2 - 5这组输出能帮你快速确认逻辑是否正确。如果你发现第二轮结果变成1 - 4 - 2 - 3 - 5恭喜你最典型的“断链”bug出现了。4.2 调试时如何快速定位断链链表调试最直观的手段就是打印。写一个简单的打印函数每轮循环末尾输出当前链表状态问题立刻原形毕露。def print_list(head): cur head while cur is not None: print(cur.val, end - ) cur cur.next print(None)这段小工具我几乎用在所有链表题上成本极低收益极高。遇到诡异 bug先打印再对照手画的图绝大多数问题都能肉眼定位。还有一种情况是你最后打印时发现死循环大概率是某个节点的next指回了前面的节点形成环。如果怀疑有环可以用快慢指针检测但更快的办法是回过头检查那三条赋值语句的顺序。我总结过一个自查口诀先存后继、再断旧链、再搭新链、最后接入头部。每一轮操作都按这个顺序执行基本不会出环。4.3 面试追问与相关变体题这道题在面试中经常附带追问。最常见的追问是如果不用虚拟头节点你怎么处理left 1的情况这就需要分类讨论代码会多一些分支但核心逻辑不变。你可以主动先写虚拟头版本的解法然后补充说明“如果不用 dummy我还得对left 1单独处理代码会比较冗余。”更进阶的追问会把这道题扩展成变体反转整个链表直接调用reverseBetween(head, 1, 链表长度)。K 个一组反转LeetCode 第 25 题核心就是反复做区间反转只是每组区间长度固定为 K。回文链表判断先找中点再反转后半段本质上是区间反转的一个应用。重排链表涉及“找中点、反转后半段、合并两条链表”同样会用到局部反转思想。能把这些变体和区间反转联系起来面试官会觉得你是真的理解了而不是背题。5. 实操心得与进阶思路5.1 迭代和递归怎么选除了迭代法这道题还有一种递归写法核心是“反转前 N 个节点”。我在面试时偶尔会作为加分项抛出。struct ListNode* successor NULL; struct ListNode* reverseN(struct ListNode* head, int n) { if (n 1) { successor head-next; return head; } struct ListNode* last reverseN(head-next, n - 1); head-next-next head; head-next successor; return last; } struct ListNode* reverseBetweenRecur(struct ListNode* head, int left, int right) { if (left 1) { return reverseN(head, right); } head-next reverseBetweenRecur(head-next, left - 1, right - 1); return head; }递归版本代码更短但有两个明显短板一是额外使用了递归栈空间复杂度 O(N)二是successor需要使用外部变量或包装类保存写起来不够“纯净”。所以在面试中我会先给迭代法再提一句递归法作为补充而不是反过来。5.2 从这道题延伸出去的通用技巧刷链表题这么多年我发现有两条通用技巧是放之四海皆准的。第一条画图。任何链表题先画几条线、几个方框理清操作前后的链接关系再动手写代码。你在图上画清楚代码就是照着图翻译。我在指导别人刷题时几乎每次都要求他们先把图按步骤画完再允许打开编辑器。第二条检查断链窗口。修改链表指针时最多同时涉及三个节点。我在每次写赋值语句前都会问自己被覆盖的那个引用还有没有别的变量指向它如果没有它就会断链。有了这个意识很多链表 bug 在写代码阶段就能避免。5.3 一道题的多种解法递归版本递归版本虽然不推荐在正式面试中作为首选但它值得你花时间理解因为递归的视角和迭代完全不同。迭代法是“从前往后逐个摘节点再插到前面”递归法是“递归到区间尾部再一层层把头节点挪到后面”。理解递归版本能加深你对“反转”本质的认知反转任意一段链表可以分解成“反转去掉第一个节点后的子段再把头节点放到子段末尾”。这种分解思想不仅适用于链表也适用于很多递归结构的问题。我个人的建议是这道题先画图走三遍迭代逻辑再手写一遍递归逻辑最后把两种方法的时空复杂度写出来对比。这个过程比单纯刷十道简单链表题都有用。这道题我刷过很多遍也反复给别人讲。每次讲完我都会强调链表的操作核心永远是指针和引用管理背模板没有出路真正理解每一步在做什么才是关键。等你把区间反转嚼透了再回头看 K 个一组反转和重排链表会发现它们没那么可怕。最后分享一个小技巧面试时写完迭代解法可以主动提一句“我还知道递归写法空间复杂度高一些但可以展开聊聊”这往往是个不错的加分点亲测有效。