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

leetcode1 仓库实战解析：反转链表 II（LeetCode 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 prev

  0206 题在仓库中覆盖 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时头节点变化的边界情形；递归反转的机制是让每个节点指向它的前驱。

算法步骤（完整继承原文档）

1. 创建一个指向head的哨兵节点，以处理边界情况。
2. 遍历left - 1步，找到left位置的前一个节点（记作prev）。
3. 确定子表头sublist_head，再走right - left步找到位于right位置的子表尾sublist_tail。
4. 保存子表之后的节点（nextNode），并把sublist_tail.next置空，从而把子表断开。
5. 递归反转该子表：基本情况直接返回单节点；否则对下一个节点递归，并让它回指当前节点。
6. 把prev接到反转后的新子表头（递归返回值），把原sublist_head（翻转后变成尾）接到nextNode。
7. 返回dummy.next。

代码实现

Python（articles/reverse-linked-list-ii.md 原文完整示例）：

# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # 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 newHead

Java 版本体现了同样的「断开 → 递归 → 重接」结构：

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 版由于Option<Box<ListNode>>的所有权模型，无法原地改写指针链，采用node.next.take()逐节点摘取、以reversed变量滚动构建反转段、最后沿reversed链找到尾部接回curr的写法，是从语言内存模型出发的一个有价值的变体。

复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$，递归调用栈的深度由列表规模决定。

解法二：递归子表（Recursion - II）——用后继节点收尾的定长反转

核心思路

这一版本不显式断开子表，而是用递归来走到反转区间的起点：当left减到 1 时，说明当前head就是反转段的头，此时交给辅助函数reverseList(node, n)去反转「从当前节点起的前right个节点」。辅助函数的关键是跟踪successor（后继节点，即反转段之后的节点）；随着递归回溯，逐层回拨指针完成反转，同时把段尾接到successor上，全程不改变区间外节点。

算法步骤（完整继承原文档）

1. 若left == 1，调用辅助函数reverseList反转前right个节点。
2. 否则，对head.next递归，并把left、right各减 1，然后把结果挂回head.next。
3. 辅助函数reverseList反转从给定节点起的n个节点：
   • 基本情况：n == 1时保存successor（下一个节点），返回当前节点；
   • 对下一个节点以n - 1递归；
   • 递归返回后，让下一个节点回指当前节点，并把当前节点的next设为保存的successor。
4. 返回反转段的新头。

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 head

Java 版本用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: pair<ListNode*, 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：迭代版与解法一结构相同，只是把子表的递归反转换成循环反转。流程是「定位边界 → 断开子表 → 原地三指针反转 → 重接两端」，全程只多走常数级别的指针操作，空间上不再依赖递归栈。

算法步骤（完整继承原文档）

1. 创建指向head的哨兵节点。
2. 走left - 1步，找到prev（子表的前驱节点）。
3. 确定子表头sublist_head，再走right - left步找到子表尾sublist_tail。
4. 保存子表后的节点nextNode，置sublist_tail.next为null完成断开。
5. 用prev、curr双指针循环反转子表：每个节点先保存next，再把curr指向prev，然后两指针同向前进。
6. 把prev.next接到反转后的新头（循环结束时的prev），把原sublist_head（现为尾）接到保存的后继节点。
7. 返回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 prev

Java 版本逻辑一致，仅把 Python 的None换成null、方法调用换成私有方法reverseList：

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) { 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，反转完成后它正好是段尾，可以直接用它把段尾接到段后节点，无需额外变量记录尾节点。

算法步骤（完整继承原文档）

1. 创建指向head的哨兵节点。
2. 走left - 1步，同时维护leftPrev（反转段前驱）与cur（待反转的第一个节点）。
3. 原地反转right - left + 1个节点：
   • 保存cur.next为tmpNext；
   • 令cur.next指向prev；
   • prev前进到cur，cur前进到tmpNext。
4. 循环结束后，prev指向反转段的新头，cur指向段后的第一个节点。
5. 把leftPrev.next.next（原始首节点，即现在的段尾）接到cur。
6. 把leftPrev.next接到prev（新头）。
7. 返回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.next

Java 版本：

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.js：JS 语言下的同题解法，可作为前端开发者阅读指针操作的参照。

复杂度

• 时间复杂度：$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