LeetCode 92 反转链表 II 图解四点法定位四个关键节点、虚拟头简化边界与多语言实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文围绕 leetcode 题解仓库中 problems/92.reverse-linked-list-ii.md 的经典解法“四点法”完整讲解如何用一趟扫描完成从位置 m 到 n 的链表区间反转并借助 thinkings/linked-list.md 中的“穿针引线”方法论解释 p1/p2/p3/p4 四个特殊节点的定位、虚拟头节点 dummy 的必要性以及反转循环中严格的指针更新顺序。读完本文你将掌握区间反转链表的标准套路四点法能独立写出 JavaScript / Python 两种实现并理解它作为 206. 反转链表 的升级版与 25. K 个一组翻转链表 之间的递进关系。一、题目描述与前置知识1.1 题目描述题目要求反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明1 ≤ m ≤ n ≤ 链表长度。示例输入: 1-2-3-4-5-NULL, m 2, n 4 输出: 1-4-3-2-5-NULL题目地址LeetCode 92. Reverse Linked List II中文版92. 反转链表 II。1.2 前置知识链表需要熟悉链表的插入、删除、遍历等基本操作以及头尾节点的边界处理。仓库中的 thinkings/basic-data-structure.md 对数组与链表的物理存储差异、链表的增删查改复杂度做了系统讲解thinkings/linked-list.md 则集中总结了链表题型的通用技巧本文的“四点法”正是其中“穿针引线”技巧的具体应用。基础版反转本题是经典反转链表题的升级版建议先掌握 206. 反转链表 的迭代写法用 pre 记录前驱、cur 记录当前节点、不断执行cur.next pre。1.3 常见出题场景原文档标注本题常见于阿里、腾讯、百度、字节等公司的面试中属于链表类题目中区间操作的代表作既能考察链表基本功又能考察边界处理能力。二、核心思路取出 → 反转 → 插回2.1 与 206 的关系本题是 206 的升级版206. 反转链表 反转的是整条链表而本题只反转中间某一区间。从算法视角看206 可以看作本题的特殊情况special case即m 1, n 链表长度时区间反转退化为整链反转。2.2 四点法的总体框架原文档给出的核心思路是核心在于取出需要反转的这一小段链表反转完后再插入到原先的链表中。以1-2-3-4-5-NULL, m 2, n 4为例需要反转的是 2、3、4 这三个节点先取出 2用cur指针指向 2当取出 3 时将 3 指向 2并把cur前移到 3依次类推处理到 4 后停止这样得到一条新链表4-3-2cur指针指向 4对于原链表有两个位置很关键m 位置的前一个节点 1和n 位置的后一个节点 5它们决定了反转后的片段该接到哪里。用pre指针记录节点 1 的位置当节点 4 被取走后节点 5 的位置也需要记下来最后把反转后的片段新链表4-3-2接入原链表得到1-4-3-2-5-NULL。2.3 四个关键节点p1 / p2 / p3 / p4实现时用四个指针原文档称之为“四点法”在一趟遍历中记录四个特殊位置指针记录位置作用p1索引m - 1处的节点反转区间的前驱反转完成后p1.next要指向p3p2索引m处的节点反转区间的原头节点反转完成后它变成片段尾需要p2.next p4p3索引n处的节点反转区间的原尾节点反转完成后它变成片段头由p1或 dummy 指向p4索引n 1处的节点反转区间的后继是p2反转后要接上的位置一趟遍历结束后只需要两条拼接语句即可完成“穿针引线”p1.next p3 # 前驱接上反转后的片段头 p2.next p4 # 反转后的片段尾接上原链表后继这与 thinkings/linked-list.md 中“穿针引线”小节的描述完全一致给断点从左到右编号为 a、b、c、d其中a、d 分别是需要反转部分的前驱和后继不参与反转b 和 c 是需要反转部分的头和尾参与反转找到后直接执行a.next c、b.next d。这里的 a、b、c、d 即对应四点法中的 p1、p2、p3、p4。三、为什么必须使用虚拟头节点 dummy原文档专门强调了一个初学极易踩坑的点直接返回 head 是不行的。当m ! 1时p1存在p1.next p3可以正常拼接返回head没有问题但只要m 1反转区间的头就是链表头此时p1为None没有前驱节点可以接上p3。如果仍然返回headhead指向的节点在反转后已经不是新链表的头结果必然出错。解决办法是引入虚拟头节点dummydummy ListNode(0) dummy.next head让dummy充当head的“前驱”统一处理“是否有 p1”的两种情况最终统一返回dummy.next无论m是否为 1 都安全。此外原文档还提醒如果链表长度小于 4p1、p2、p3、p4 中就可能存在空指针None。例如m 1, n 链表长度时p1和p4都可能为空拼接时必须充分判空防止 NPEif not p1: dummy.next p3 else: p1.next p3 p2.next p4 # p4 为空时等价于让反转后的片段尾指向 None是合法收尾四、反转循环中的指针操作顺序易错点4.1 顺序为什么不能错原文档给出的反转循环内三个关键动作顺序有严格要求先cur.next pre修改指针让当前节点指向前驱完成反转再更新p2以及p2.next其中必须设置p2.next None否则反转后的片段尾仍指向片段内旧节点形成互相引用造成无限循环最后更新pre和cur指针后移。原因在于如果p2.next None被放到最后那么cur此时已走到 n 之后会在遍历中提前断开——因为反转区间的原头p2的next还挂着旧链接指针推进时会把已经反转好的片段重新串回去导致结果错误甚至死循环。4.2 核心遍历循环伪代码/框架while cur: i 1 if i m - 1: p1 cur # 记录前驱 next cur.next # 先保存后继顺序关键点 if m i n: # 区间内执行反转 cur.next pre if i m: p2 cur p2.next None # 断开旧链接防止互相引用 if i n: p3 cur # 记录反转区间尾 if i n 1: p4 cur # 记录反转区间后继 pre cur cur next这段框架与原文档保持一致其核心思想与 thinkings/linked-list.md 中“先穿再排后判空”的建议完全吻合“穿”指针时必须先执行next cur.next再执行cur.next pre——因为cur.next pre一旦执行cur与链表后半段就断开了此时再取cur.next得到的将是被反转后的前驱而不是原来的后继。五、关键点解析四点法用 p1、p2、p3、p4 四个变量记录四个特殊节点然后只操作这四个节点的连接方式即可逻辑清晰、不易出错链表的基本操作插入、删除、遍历的指针调整基本功特殊情况处理m 1或n 链表长度时采用虚拟头节点 dummy 简化操作用四个变量记录特殊节点然后按一定方式连接即p1.next p3、p2.next p4两条语句完成拼接注意更新 current 和 pre 的位置否则可能出现指针错乱死循环/断开。六、多语言代码实现原文档将这一解法命名为“四点法”并提供 JavaScript、Python 两种完整实现原文档同时标注支持 C。6.1 JavaScript 实现/* * lc appleetcode id92 langjavascript * * [92] Reverse Linked List II * * https://leetcode.com/problems/reverse-linked-list-ii/description/ */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} head * param {number} m * param {number} n * return {ListNode} */ var reverseBetween function (head, m, n) { // 虚拟节点简化操作 const dummyHead { next: head, }; let cur dummyHead.next; // 当前遍历的节点 let pre cur; // 因为要反转因此我们需要记住前一个节点 let index 0; // 链表索引用来判断是否是特殊位置头尾位置 // 上面提到的四个特殊节点 let p1 (p2 p3 p4 null); while (cur) { const next cur.next; index; // 对 (m - n) 范围内的节点进行反转 if (index m index n) { cur.next pre; } // 下面四个if都是边界, 用于更新四个特殊节点的值 if (index m - 1) { p1 cur; } if (index m) { p2 cur; } if (index n) { p3 cur; } if (index n 1) { p4 cur; } pre cur; cur next; } // 两个链表合并起来 (p1 || dummyHead).next p3; // 特殊情况需要考虑 p2.next p4; return dummyHead.next; };6.2 Python 实现class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) - ListNode: if not head.next or n 1: return head dummy ListNode() dummy.next head pre None cur head i 0 p1 p2 p3 p4 None while cur: i 1 next cur.next if m i n: cur.next pre if i m - 1: p1 cur if i m: p2 cur if i n: p3 cur if i n 1: p4 cur pre cur cur next if not p1: dummy.next p3 else: p1.next p3 p2.next p4 return dummy.next6.3 复杂度分析时间复杂度$O(N)$其中 N 为链表长度全程只遍历一遍链表空间复杂度$O(1)$只使用常数个指针变量不含递归栈。七、方法论延伸从“四点法”看链表拼接类题目的共性7.1 “穿针引线”技巧thinkings/linked-list.md 将这类“反转链表中间一部分”的问题归纳为链表第二大考点——拼接链表并命名为“穿针引线”该方法通常不是最优解但好理解、方便书写、不易出错推荐新手使用做法从左到右给断点编号涉及四个节点 a、b、c、d对应四点法 p1、p3、p2、p4 的定位逻辑找到后直接穿针引线拼接仓库明确指出25. K 个一组翻转链表、61. 旋转链表与本题 92 都采用了这一思路。7.2 仓库内的交叉印证problems/25.reverse-nodes-in-k-groups.md 在讲解 K 个一组翻转时明确写道“如果这道题你按照 92.reverse-linked-list-ii 提到的p1, p2, p3, p4四点法的思路来思考的话会很清晰”并在文末把本题列为相关题目——可见四点法是整个仓库链表专题的基础套路thinkings/linked-list.md 中“先穿再排后判空”小节以反转循环中next cur.next与cur.next pre的先后顺序为例解释了指针修改顺序的重要性与本文第四章的易错点分析互相印证。八、相关题目206. 反转链表本题的基础版反转整条链表是四点法的退化情形25. K 个一组翻转链表在本题基础上进一步升级按 K 个一组反复使用区间反转与穿针引线拼接适合在掌握四点法后继续挑战。小结区间反转链表92 题的核心套路可以浓缩为四步一趟遍历记录四个关键节点p1/p2/p3/p4→ 区间内逐节点反转并断开旧链接 → 用虚拟头 dummy 统一处理 m1 的边界 → 两条拼接语句完成穿针引线。配合 O(N) 时间、O(1) 空间的复杂度这一解法兼具正确性、简洁性与可推广性是链表类题目中值得反复练习的模板解法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 92 反转链表 II 图解：四点法定位四个关键节点、虚拟头简化边界与多语言实现
LeetCode 92 反转链表 II 图解四点法定位四个关键节点、虚拟头简化边界与多语言实现【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文围绕 leetcode 题解仓库中 problems/92.reverse-linked-list-ii.md 的经典解法“四点法”完整讲解如何用一趟扫描完成从位置 m 到 n 的链表区间反转并借助 thinkings/linked-list.md 中的“穿针引线”方法论解释 p1/p2/p3/p4 四个特殊节点的定位、虚拟头节点 dummy 的必要性以及反转循环中严格的指针更新顺序。读完本文你将掌握区间反转链表的标准套路四点法能独立写出 JavaScript / Python 两种实现并理解它作为 206. 反转链表 的升级版与 25. K 个一组翻转链表 之间的递进关系。一、题目描述与前置知识1.1 题目描述题目要求反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明1 ≤ m ≤ n ≤ 链表长度。示例输入: 1-2-3-4-5-NULL, m 2, n 4 输出: 1-4-3-2-5-NULL题目地址LeetCode 92. Reverse Linked List II中文版92. 反转链表 II。1.2 前置知识链表需要熟悉链表的插入、删除、遍历等基本操作以及头尾节点的边界处理。仓库中的 thinkings/basic-data-structure.md 对数组与链表的物理存储差异、链表的增删查改复杂度做了系统讲解thinkings/linked-list.md 则集中总结了链表题型的通用技巧本文的“四点法”正是其中“穿针引线”技巧的具体应用。基础版反转本题是经典反转链表题的升级版建议先掌握 206. 反转链表 的迭代写法用 pre 记录前驱、cur 记录当前节点、不断执行cur.next pre。1.3 常见出题场景原文档标注本题常见于阿里、腾讯、百度、字节等公司的面试中属于链表类题目中区间操作的代表作既能考察链表基本功又能考察边界处理能力。二、核心思路取出 → 反转 → 插回2.1 与 206 的关系本题是 206 的升级版206. 反转链表 反转的是整条链表而本题只反转中间某一区间。从算法视角看206 可以看作本题的特殊情况special case即m 1, n 链表长度时区间反转退化为整链反转。2.2 四点法的总体框架原文档给出的核心思路是核心在于取出需要反转的这一小段链表反转完后再插入到原先的链表中。以1-2-3-4-5-NULL, m 2, n 4为例需要反转的是 2、3、4 这三个节点先取出 2用cur指针指向 2当取出 3 时将 3 指向 2并把cur前移到 3依次类推处理到 4 后停止这样得到一条新链表4-3-2cur指针指向 4对于原链表有两个位置很关键m 位置的前一个节点 1和n 位置的后一个节点 5它们决定了反转后的片段该接到哪里。用pre指针记录节点 1 的位置当节点 4 被取走后节点 5 的位置也需要记下来最后把反转后的片段新链表4-3-2接入原链表得到1-4-3-2-5-NULL。2.3 四个关键节点p1 / p2 / p3 / p4实现时用四个指针原文档称之为“四点法”在一趟遍历中记录四个特殊位置指针记录位置作用p1索引m - 1处的节点反转区间的前驱反转完成后p1.next要指向p3p2索引m处的节点反转区间的原头节点反转完成后它变成片段尾需要p2.next p4p3索引n处的节点反转区间的原尾节点反转完成后它变成片段头由p1或 dummy 指向p4索引n 1处的节点反转区间的后继是p2反转后要接上的位置一趟遍历结束后只需要两条拼接语句即可完成“穿针引线”p1.next p3 # 前驱接上反转后的片段头 p2.next p4 # 反转后的片段尾接上原链表后继这与 thinkings/linked-list.md 中“穿针引线”小节的描述完全一致给断点从左到右编号为 a、b、c、d其中a、d 分别是需要反转部分的前驱和后继不参与反转b 和 c 是需要反转部分的头和尾参与反转找到后直接执行a.next c、b.next d。这里的 a、b、c、d 即对应四点法中的 p1、p2、p3、p4。三、为什么必须使用虚拟头节点 dummy原文档专门强调了一个初学极易踩坑的点直接返回 head 是不行的。当m ! 1时p1存在p1.next p3可以正常拼接返回head没有问题但只要m 1反转区间的头就是链表头此时p1为None没有前驱节点可以接上p3。如果仍然返回headhead指向的节点在反转后已经不是新链表的头结果必然出错。解决办法是引入虚拟头节点dummydummy ListNode(0) dummy.next head让dummy充当head的“前驱”统一处理“是否有 p1”的两种情况最终统一返回dummy.next无论m是否为 1 都安全。此外原文档还提醒如果链表长度小于 4p1、p2、p3、p4 中就可能存在空指针None。例如m 1, n 链表长度时p1和p4都可能为空拼接时必须充分判空防止 NPEif not p1: dummy.next p3 else: p1.next p3 p2.next p4 # p4 为空时等价于让反转后的片段尾指向 None是合法收尾四、反转循环中的指针操作顺序易错点4.1 顺序为什么不能错原文档给出的反转循环内三个关键动作顺序有严格要求先cur.next pre修改指针让当前节点指向前驱完成反转再更新p2以及p2.next其中必须设置p2.next None否则反转后的片段尾仍指向片段内旧节点形成互相引用造成无限循环最后更新pre和cur指针后移。原因在于如果p2.next None被放到最后那么cur此时已走到 n 之后会在遍历中提前断开——因为反转区间的原头p2的next还挂着旧链接指针推进时会把已经反转好的片段重新串回去导致结果错误甚至死循环。4.2 核心遍历循环伪代码/框架while cur: i 1 if i m - 1: p1 cur # 记录前驱 next cur.next # 先保存后继顺序关键点 if m i n: # 区间内执行反转 cur.next pre if i m: p2 cur p2.next None # 断开旧链接防止互相引用 if i n: p3 cur # 记录反转区间尾 if i n 1: p4 cur # 记录反转区间后继 pre cur cur next这段框架与原文档保持一致其核心思想与 thinkings/linked-list.md 中“先穿再排后判空”的建议完全吻合“穿”指针时必须先执行next cur.next再执行cur.next pre——因为cur.next pre一旦执行cur与链表后半段就断开了此时再取cur.next得到的将是被反转后的前驱而不是原来的后继。五、关键点解析四点法用 p1、p2、p3、p4 四个变量记录四个特殊节点然后只操作这四个节点的连接方式即可逻辑清晰、不易出错链表的基本操作插入、删除、遍历的指针调整基本功特殊情况处理m 1或n 链表长度时采用虚拟头节点 dummy 简化操作用四个变量记录特殊节点然后按一定方式连接即p1.next p3、p2.next p4两条语句完成拼接注意更新 current 和 pre 的位置否则可能出现指针错乱死循环/断开。六、多语言代码实现原文档将这一解法命名为“四点法”并提供 JavaScript、Python 两种完整实现原文档同时标注支持 C。6.1 JavaScript 实现/* * lc appleetcode id92 langjavascript * * [92] Reverse Linked List II * * https://leetcode.com/problems/reverse-linked-list-ii/description/ */ /** * Definition for singly-linked list. * function ListNode(val) { * this.val val; * this.next null; * } */ /** * param {ListNode} head * param {number} m * param {number} n * return {ListNode} */ var reverseBetween function (head, m, n) { // 虚拟节点简化操作 const dummyHead { next: head, }; let cur dummyHead.next; // 当前遍历的节点 let pre cur; // 因为要反转因此我们需要记住前一个节点 let index 0; // 链表索引用来判断是否是特殊位置头尾位置 // 上面提到的四个特殊节点 let p1 (p2 p3 p4 null); while (cur) { const next cur.next; index; // 对 (m - n) 范围内的节点进行反转 if (index m index n) { cur.next pre; } // 下面四个if都是边界, 用于更新四个特殊节点的值 if (index m - 1) { p1 cur; } if (index m) { p2 cur; } if (index n) { p3 cur; } if (index n 1) { p4 cur; } pre cur; cur next; } // 两个链表合并起来 (p1 || dummyHead).next p3; // 特殊情况需要考虑 p2.next p4; return dummyHead.next; };6.2 Python 实现class Solution: def reverseBetween(self, head: ListNode, m: int, n: int) - ListNode: if not head.next or n 1: return head dummy ListNode() dummy.next head pre None cur head i 0 p1 p2 p3 p4 None while cur: i 1 next cur.next if m i n: cur.next pre if i m - 1: p1 cur if i m: p2 cur if i n: p3 cur if i n 1: p4 cur pre cur cur next if not p1: dummy.next p3 else: p1.next p3 p2.next p4 return dummy.next6.3 复杂度分析时间复杂度$O(N)$其中 N 为链表长度全程只遍历一遍链表空间复杂度$O(1)$只使用常数个指针变量不含递归栈。七、方法论延伸从“四点法”看链表拼接类题目的共性7.1 “穿针引线”技巧thinkings/linked-list.md 将这类“反转链表中间一部分”的问题归纳为链表第二大考点——拼接链表并命名为“穿针引线”该方法通常不是最优解但好理解、方便书写、不易出错推荐新手使用做法从左到右给断点编号涉及四个节点 a、b、c、d对应四点法 p1、p3、p2、p4 的定位逻辑找到后直接穿针引线拼接仓库明确指出25. K 个一组翻转链表、61. 旋转链表与本题 92 都采用了这一思路。7.2 仓库内的交叉印证problems/25.reverse-nodes-in-k-groups.md 在讲解 K 个一组翻转时明确写道“如果这道题你按照 92.reverse-linked-list-ii 提到的p1, p2, p3, p4四点法的思路来思考的话会很清晰”并在文末把本题列为相关题目——可见四点法是整个仓库链表专题的基础套路thinkings/linked-list.md 中“先穿再排后判空”小节以反转循环中next cur.next与cur.next pre的先后顺序为例解释了指针修改顺序的重要性与本文第四章的易错点分析互相印证。八、相关题目206. 反转链表本题的基础版反转整条链表是四点法的退化情形25. K 个一组翻转链表在本题基础上进一步升级按 K 个一组反复使用区间反转与穿针引线拼接适合在掌握四点法后继续挑战。小结区间反转链表92 题的核心套路可以浓缩为四步一趟遍历记录四个关键节点p1/p2/p3/p4→ 区间内逐节点反转并断开旧链接 → 用虚拟头 dummy 统一处理 m1 的边界 → 两条拼接语句完成穿针引线。配合 O(N) 时间、O(1) 空间的复杂度这一解法兼具正确性、简洁性与可推广性是链表类题目中值得反复练习的模板解法。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考