leetcode1 仓库实战解析：反转链表 II（LeetCode 92）的递归与原地迭代四种解法

leetcode1 仓库实战解析反转链表 IILeetCode 92的递归与原地迭代四种解法【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于 leetcode1 仓库中的文档 articles/reverse-linked-list-ii.md系统讲解 LeetCode 92「反转链表 II」的完整求解体系从问题拆解、哨兵节点技巧到四种可落地的实现路线递归反转、递归子表、迭代断开-重连、单趟原地反转并逐一对比仓库中 Python / C / Java / Kotlin 等语言的实际解法代码帮助读者掌握链表段定位、指针拆接与复杂度权衡的全套实战能力。问题定义与前置知识反转链表 II 的标准题面与 cpp/0092-reverse-linked-list-ii.cpp 顶部注释一致Given the head of a singly linked list and two integersleftandrightwhereleft right, reverse the nodes of the list from positionleftto positionright, and return the reversed list.经典示例输入head [1,2,3,4,5], left 2, right 4输出[1,4,3,2,5]即把第 2 到第 4 位这一段翻转后重新接回原链。根据原文档的 Prerequisites 部分动手之前需要掌握四个前置技能完整链表反转Reverse Linked List Basic本题的段内反转完全建立在标准反转技巧之上仓库中对应题解为 python/0206-reverse-linked-list.py其核心就是三指针prev / curr / temp循环class Solution: def reverseList(self, head: ListNode) - ListNode: prev, curr None, head while curr: temp curr.next curr.next prev prev curr curr temp return prev0206 题在仓库中覆盖 c、csharp、dart、go、java、javascript、kotlin、python、ruby、rust、scala、swift、typescript 十余种语言如 rust/0206-reverse-linked-list.rs、go/0206-reverse-linked-list.go可作为基础题的多语言参照。哨兵节点Dummy Node技巧当left 1时反转会让原head失效哨兵节点提供了一个稳定的锚点避免对头部特判。按位置遍历链表通过计数走到指定位置本题需要精确定位left的前驱节点与right尾节点。多指针协同管理断开disconnect、反转reverse、重连reconnect三个阶段各有不同的指针职责错序更新是本题最常见的错误来源。解法一递归反转Recursion - I——断开子表 递归翻转子段核心思路原文档 Intuition 的表述是先定位子表的边界把它从主链中断开用标准反转把它翻转再把碎片重接回去哨兵节点负责简化left 1时头节点变化的边界情形递归反转的机制是让每个节点指向它的前驱。算法步骤完整继承原文档创建一个指向head的哨兵节点以处理边界情况。遍历left - 1步找到left位置的前一个节点记作prev。确定子表头sublist_head再走right - left步找到位于right位置的子表尾sublist_tail。保存子表之后的节点nextNode并把sublist_tail.next置空从而把子表断开。递归反转该子表基本情况直接返回单节点否则对下一个节点递归并让它回指当前节点。把prev接到反转后的新子表头递归返回值把原sublist_head翻转后变成尾接到nextNode。返回dummy.next。代码实现Pythonarticles/reverse-linked-list-ii.md 原文完整示例# Definition for singly-linked list. # class ListNode: # def __init__(self, val0, nextNone): # self.val val # self.next next class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(0) dummy.next head prev dummy for _ in range(left - 1): prev prev.next sublist_head prev.next sublist_tail sublist_head for _ in range(right - left): sublist_tail sublist_tail.next next_node sublist_tail.next sublist_tail.next None reversed_sublist self.reverseList(sublist_head) prev.next reversed_sublist sublist_head.next next_node return dummy.next def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: if not head: return None newHead head if head.next: newHead self.reverseList(head.next) head.next.next head head.next None return newHeadJava 版本体现了同样的「断开 → 递归 → 重接」结构public class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; for (int i 0; i left - 1; i) { prev prev.next; } ListNode sublistHead prev.next; ListNode sublistTail sublistHead; for (int i 0; i right - left; i) { sublistTail sublistTail.next; } ListNode nextNode sublistTail.next; sublistTail.next null; prev.next reverseList(sublistHead); sublistHead.next nextNode; return dummy.next; } private ListNode reverseList(ListNode head) { if (head null || head.next null) { return head; } ListNode newHead reverseList(head.next); head.next.next head; head.next null; return newHead; } }C 版本的差异在于哨兵节点是栈上的ListNode dummy(0)prev取其地址dummy断开用nullptr其余逻辑与 Python 一一对应class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; for (int i 0; i left - 1; i) { prev prev-next; } ListNode* sublistHead prev-next; ListNode* sublistTail sublistHead; for (int i 0; i right - left; i) { sublistTail sublistTail-next; } ListNode* nextNode sublistTail-next; sublistTail-next nullptr; prev-next reverseList(sublistHead); sublistHead-next nextNode; return dummy.next; } private: ListNode* reverseList(ListNode* head) { if (!head || !head-next) { return head; } ListNode* newHead reverseList(head-next); head-next-next head; head-next nullptr; return newHead; } };JavaScript 版本使用闭包函数reverseList代替方法ListNode构造函数原生支持(val, next)双参初始化class Solution { /** * param {ListNode} head * param {number} left * param {number} right * return {ListNode} */ reverseBetween(head, left, right) { const reverseList (head) { if (!head || !head.next) { return head; } const newHead reverseList(head.next); head.next.next head; head.next null; return newHead; }; const dummy new ListNode(0, head); let prev dummy; for (let i 0; i left - 1; i) { prev prev.next; } const sublistHead prev.next; let sublistTail sublistHead; for (let i 0; i right - left; i) { sublistTail sublistTail.next; } const nextNode sublistTail.next; sublistTail.next null; prev.next reverseList(sublistHead); sublistHead.next nextNode; return dummy.next; } }此外原文档还给出 C#、Go、Kotlin、Swift、Rust 的同构实现其中 Rust 版由于OptionBoxListNode的所有权模型无法原地改写指针链采用node.next.take()逐节点摘取、以reversed变量滚动构建反转段、最后沿reversed链找到尾部接回curr的写法是从语言内存模型出发的一个有价值的变体。复杂度时间复杂度$O(n)$空间复杂度$O(n)$递归调用栈的深度由列表规模决定。解法二递归子表Recursion - II——用后继节点收尾的定长反转核心思路这一版本不显式断开子表而是用递归来走到反转区间的起点当left减到 1 时说明当前head就是反转段的头此时交给辅助函数reverseList(node, n)去反转「从当前节点起的前right个节点」。辅助函数的关键是跟踪successor后继节点即反转段之后的节点随着递归回溯逐层回拨指针完成反转同时把段尾接到successor上全程不改变区间外节点。算法步骤完整继承原文档若left 1调用辅助函数reverseList反转前right个节点。否则对head.next递归并把left、right各减 1然后把结果挂回head.next。辅助函数reverseList反转从给定节点起的n个节点基本情况n 1时保存successor下一个节点返回当前节点对下一个节点以n - 1递归递归返回后让下一个节点回指当前节点并把当前节点的next设为保存的successor。返回反转段的新头。Python 版本用元组(new_head, next_node)双返回值来传递「新头 段后节点」无需成员变量class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: def reverseList(node, n): if n 1: return node, node.next new_head, next_node reverseList(node.next, n - 1) node.next.next node node.next next_node return new_head, next_node if left 1: new_head, _ reverseList(head, right) return new_head head.next self.reverseBetween(head.next, left - 1, right - 1) return headJava 版本用ListNode[]二元组替代元组语义与 Python 完全一致public class Solution { private ListNode[] reverseList(ListNode node, int n) { if (n 1) { return new ListNode[] { node, node.next }; } ListNode[] result reverseList(node.next, n - 1); node.next.next node; node.next result[1]; return new ListNode[] { result[0], node.next }; } public ListNode reverseBetween(ListNode head, int left, int right) { if (left 1) { return reverseList(head, right)[0]; } head.next reverseBetween(head.next, left - 1, right - 1); return head; } }C 版本则用std::pair承载同样的二元组class Solution { private: pairListNode*, ListNode* reverseList(ListNode* node, int n) { if (n 1) { return {node, node-next}; } auto result reverseList(node-next, n - 1); node-next-next node; node-next result.second; return {result.first, node-next}; } public: ListNode* reverseBetween(ListNode* head, int left, int right) { if (left 1) { return reverseList(head, right).first; } head-next reverseBetween(head-next, left - 1, right - 1); return head; } };原文档中 C# 与 Kotlin 版本展示了另一种风格把successor声明为类成员变量在递归基本情况里写入、在回溯层读出从而辅助函数只需返回新头一个值。Go 版本则利用闭包捕获外层successor变量效果与成员变量等价但保持了函数级封装func reverseBetween(head *ListNode, left int, right int) *ListNode { var successor *ListNode var reverseList func(*ListNode, int) *ListNode reverseList func(node *ListNode, n int) *ListNode { if n 1 { successor node.Next return node } newHead : reverseList(node.Next, n-1) node.Next.Next node node.Next successor return newHead } if left 1 { return reverseList(head, right) } head.Next reverseBetween(head.Next, left-1, right-1) return head }从源码结构看「成员/闭包变量传递 successor」与「返回值传递二元组」是同一算法的两种数据流设计前者省去构造返回值对象但状态隐式、不易并发复用后者纯函数式、更易推理。复杂度时间复杂度$O(n)$空间复杂度$O(n)$同样受递归栈深度限制一次遍历最多两层嵌套递归外层推进left 内层反转right个节点总深度为 $O(n)$。解法三迭代断开-重连Iteration - I——三指针循环替换递归反转核心思路原文档 Intuition迭代版与解法一结构相同只是把子表的递归反转换成循环反转。流程是「定位边界 → 断开子表 → 原地三指针反转 → 重接两端」全程只多走常数级别的指针操作空间上不再依赖递归栈。算法步骤完整继承原文档创建指向head的哨兵节点。走left - 1步找到prev子表的前驱节点。确定子表头sublist_head再走right - left步找到子表尾sublist_tail。保存子表后的节点nextNode置sublist_tail.next为null完成断开。用prev、curr双指针循环反转子表每个节点先保存next再把curr指向prev然后两指针同向前进。把prev.next接到反转后的新头循环结束时的prev把原sublist_head现为尾接到保存的后继节点。返回dummy.next。Python 版本反转部分即 0206 题的标准三指针循环class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(0) dummy.next head prev dummy for _ in range(left - 1): prev prev.next sublist_head prev.next sublist_tail sublist_head for _ in range(right - left): sublist_tail sublist_tail.next next_node sublist_tail.next sublist_tail.next None reversed_sublist self.reverseList(sublist_head) prev.next reversed_sublist sublist_head.next next_node return dummy.next def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]: prev, curr None, head while curr: temp curr.next curr.next prev prev curr curr temp return prevJava 版本逻辑一致仅把 Python 的None换成null、方法调用换成私有方法reverseListpublic class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode prev dummy; for (int i 0; i left - 1; i) { prev prev.next; } ListNode sublistHead prev.next; ListNode sublistTail sublistHead; for (int i 0; i right - left; i) { sublistTail sublistTail.next; } ListNode nextNode sublistTail.next; sublistTail.next null; prev.next reverseList(sublistHead); sublistHead.next nextNode; return dummy.next; } private ListNode reverseList(ListNode head) { ListNode prev null; ListNode curr head; while (curr ! null) { ListNode temp curr.next; curr.next prev; prev curr; curr temp; } return prev; } }C 版本中注意prev既是定位用的前驱指针、又在reverseList内部复用为反转循环指针——两个作用域的prev不要混淆这也是原文档 C# 版本额外声明局部ListNode prev null;的原因class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* prev dummy; for (int i 0; i left - 1; i) { prev prev-next; } ListNode* sublistHead prev-next; ListNode* sublistTail sublistHead; for (int i 0; i right - left; i) { sublistTail sublistTail-next; } ListNode* nextNode sublistTail-next; sublistTail-next nullptr; prev-next reverseList(sublistHead); sublistHead-next nextNode; return dummy.next; } private: ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* temp curr-next; curr-next prev; prev curr; curr temp; } return prev; } };原文档同时提供了 JavaScript、C#、Go、Kotlin、Swift、Rust 的对应实现模式均与上述三者同构。复杂度时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间不再依赖递归栈。解法四单趟原地反转Iteration - II——不显式断链的 head-insertion 变体核心思路原文档 Intuition这一版不做显式断开在单趟遍历中逐条翻转指向。定位到反转起点前一个节点后每前进一个节点就把它的next拨向prev初始为null于是这些节点被依次「插」到反转段的最前面。关键在于全程保留对原sublist_head的引用——它是leftPrev.next反转完成后它正好是段尾可以直接用它把段尾接到段后节点无需额外变量记录尾节点。算法步骤完整继承原文档创建指向head的哨兵节点。走left - 1步同时维护leftPrev反转段前驱与cur待反转的第一个节点。原地反转right - left 1个节点保存cur.next为tmpNext令cur.next指向prevprev前进到curcur前进到tmpNext。循环结束后prev指向反转段的新头cur指向段后的第一个节点。把leftPrev.next.next原始首节点即现在的段尾接到cur。把leftPrev.next接到prev新头。返回dummy.next。Python 版本注意最后两行接线语句的顺序必须先写leftPrev.next.next cur此时leftPrev.next还是原首节点再写leftPrev.next prev否则首节点引用被覆盖后段尾就找不回了class Solution: def reverseBetween(self, head: Optional[ListNode], left: int, right: int) - Optional[ListNode]: dummy ListNode(0, head) leftPrev, cur dummy, head for _ in range(left - 1): leftPrev, cur cur, cur.next prev None for _ in range(right - left 1): tmpNext cur.next cur.next prev prev, cur cur, tmpNext leftPrev.next.next cur leftPrev.next prev return dummy.nextJava 版本public class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy new ListNode(0); dummy.next head; ListNode leftPrev dummy, cur head; for (int i 0; i left - 1; i) { leftPrev cur; cur cur.next; } ListNode prev null; for (int i 0; i right - left 1; i) { ListNode tmpNext cur.next; cur.next prev; prev cur; cur tmpNext; } leftPrev.next.next cur; leftPrev.next prev; return dummy.next; } }C 版本与 Java 逐行对应仅访问符不同class Solution { public: ListNode* reverseBetween(ListNode* head, int left, int right) { ListNode dummy(0); dummy.next head; ListNode* leftPrev dummy; ListNode* cur head; for (int i 0; i left - 1; i) { leftPrev cur; cur cur-next; } ListNode* prev nullptr; for (int i 0; i right - left 1; i) { ListNode* tmpNext cur-next; cur-next prev; prev cur; cur tmpNext; } leftPrev-next-next cur; leftPrev-next prev; return dummy.next; } };仓库中的对应实现这一「单趟原地反转」思路正是仓库实际解法采用的方案python/0092-reverse-linked-list-ii.py与上节 Python 版逐行一致且注释标注了三个阶段的语义——「1) reach node at position left」「2) reverse from left to right」「3) Update pointers」并特别注明cur is node after right、prev is right是理解指针终态的最好注释。cpp/0092-reverse-linked-list-ii.cpp同样的单趟结构变量命名为leftConnector对应leftPrev与temp对应cur文件头部注释明确写出Time complexity: O(n)、Space complexity: O(1)与本文复杂度结论吻合。kotlin/0092-reverse-linked-list-ii.kt从源码结构看它采用同一思想的节点搬移写法——不逐条拨指针而是把start节点逐个从段首摘出、挂到pre段前驱之后start?.next end?.next; end?.next pre?.next; pre?.next end效果等价于 head-insertion但每个节点只移动一次引用链是同一复杂度下的另一实现风格。javascript/0092-reverse-linked-list-ii.jsJS 语言下的同题解法可作为前端开发者阅读指针操作的参照。复杂度时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间。四种解法横向对比解法断链方式反转手段时间空间核心风险点解法一 Recursion I显式断开sublist_tail.next null递归回拨指针$O(n)$$O(n)$ 递归栈忘记把原头接到nextNode解法二 Recursion II不显式断链用successor收尾递归 定长计数$O(n)$$O(n)$ 递归栈successor的保存/传递时机解法三 Iteration I显式断开三指针循环$O(n)$$O(1)$内外层prev变量重名混淆解法四 Iteration II不显式断链单趟 head-insertion$O(n)$$O(1)$最后两步接线顺序写反从源码结构看可以推断出各语言实现的选型倾向Python / JavaScript / C / Java / Kotlin 等语言的 0092 解法普遍采用 $O(1)$ 空间的迭代方案如 python/0092-reverse-linked-list-ii.py、cpp/0092-reverse-linked-list-ii.cpp而 java/0092-reverse-linked-list-ii.java 则展示了「断开子表 递归反转」的解法一风格并对left right、空链做了提前返回的特判属于防御性编程的补充细节。常见陷阱Common Pitfalls原文档总结了三个高频错误逐一结合代码位置说明1. 没有用哨兵节点处理left 1的边界当left等于 1 时反转后整个列表的头都会变化。没有哨兵节点的话反转完成后会丢失新头的引用无法返回正确结果。哨兵节点提供了一个稳定的锚点所有接线路径统一写成prev.next ...其中prev可能是哨兵本身从而消除了「首节点要特判」的分支。四个解法全部以dummy开头、以dummy.next结尾正是这个原因。2. 反转后忘记重接子表的两端反转完成后必须把两端都接回主链。常见错误是只接了一端要么忘了把left前驱接到新子表头prev.next reversed_sublist要么忘了把新子表尾接到right之后的节点sublist_head.next next_node。两端缺一不可任断一端都会造成链表截断。3. 单趟反转中指针更新顺序错误解法四需要同时维护leftPrev、prev、cur多个指针。典型错误是先执行leftPrev.next prev再去读leftPrev.next.next因为leftPrev.next初始指向原首节点翻转后它恰好是段尾一旦提前被新头覆盖段尾引用就再也取不回来了。对照 python/0092-reverse-linked-list-ii.py 中先leftPrev.next.next cur、后leftPrev.next prev的两行顺序即可确认这一点——原文档明确指出「必须在用leftPrev.next访问原sublist_head之前先保存或正确使用该引用再把它覆盖为新头」。延伸阅读与相关文件本文主体文档articles/reverse-linked-list-ii.md前置题「反转链表」文档articles/reverse-linked-list.md前置题解法三指针循环多语言python/0206-reverse-linked-list.py、cpp/0206-reverse-linked-list.cpp本题 0092 仓库解法python/0092-reverse-linked-list-ii.py、cpp/0092-reverse-linked-list-ii.cpp、java/0092-reverse-linked-list-ii.java、kotlin/0092-reverse-linked-list-ii.kt、javascript/0092-reverse-linked-list-ii.js掌握本文的四条路线后推荐的学习顺序是先吃透解法三/四的迭代版本$O(1)$ 空间、面试首选再理解解法一的「断开-重接」抽象模型它是解法三的直接原型最后以解法二作为递归思维的训练。仓库中 python/0092-reverse-linked-list-ii.py 与 cpp/0092-reverse-linked-list-ii.cpp 的逐行注释可以直接作为调试断点式的阅读指南单步执行两个 for 循环记录leftPrev / prev / cur在每轮循环后的指向就能完整复现本文的指针演变过程。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考