反转链表 II（LeetCode 92）

字数 1878 2025-12-12 19:15:58

反转链表 II（LeetCode 92）

题目描述：
给你单链表的头指针 head 和两个整数 left 和 right，其中 left ≤ right。请你反转从位置 left 到位置 right 的链表节点，并返回反转后的链表。
要求：只使用一趟扫描完成反转。

示例：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
解释：原始链表 1→2→3→4→5，反转位置 2 到 4 的节点后变为 1→4→3→2→5。

解题步骤：
这是一个在单链表中反转指定区间的经典问题，我们可以用“头插法”的思想在一趟扫描中完成。

创建哑结点（dummy node）
为了方便处理 left=1 的情况（即从头节点开始反转），我们在原链表头部前添加一个哑结点 dummy，dummy.next = head。这样所有节点都有一个统一的前驱，不需要特殊处理头节点变化。
定位关键节点
我们需要找到四个关键位置：
- pre_left：要反转区间的前一个节点，最终用于连接反转后的新头。
- left_node：要反转区间的第一个节点。
- right_node：要反转区间的最后一个节点。
- suc_right：要反转区间的后一个节点，最终用于连接反转后的剩余链表。
  由于 left 和 right 可能很大，我们通过指针移动来定位，而不是用数组存储。
第一步：找到 pre_left 和 left_node
从 dummy 开始，向前移动 left-1 步，即可到达 pre_left。
然后 left_node = pre_left.next。
注意：如果 left=1，pre_left 就是 dummy，left_node 就是原 head。
第二步：反转区间 [left, right] 的链表
从 left_node 开始，到 right_node 结束，我们需要反转这个子链表。
使用三个指针进行反转：
- prev = null（反转后的新头）
- curr = left_node（当前要处理的节点）
- for 循环执行 (right-left+1) 次，即区间长度次迭代。
  在每次循环中：
  a. 保存下一个节点：next_node = curr.next
  b. 反转指针：curr.next = prev
  c. 更新指针：prev = curr, curr = next_node
  循环结束后：
- prev 指向反转后的新头，即原 right_node。
- curr 指向 suc_right，即原 right_node 的下一个节点。
  此时，子链表已经独立反转，但还未与前后部分连接。
第三步：重新连接链表
现在我们有：
- pre_left 指向 left_node 的前一个节点。
- left_node 现在是反转后的最后一个节点（因为它是原子链表的第一个节点，反转后变成最后一个）。
- prev 是反转后的新头（原 right_node）。
- curr 是 suc_right（原 right_node 的下一个节点）。
  连接步骤：
  a. 将 pre_left.next 指向 prev（新头）。
  b. 将 left_node.next 指向 curr（剩余链表）。
  这样整个链表就重新连接好了。
返回结果
最终返回 dummy.next，即新链表的头节点。

示例推演（head = [1,2,3,4,5], left=2, right=4）：

初始：dummy(0)→1→2→3→4→5
定位：pre_left = 节点1, left_node = 节点2
反转区间：
初始：prev=null, curr=2
第一次：next=3, 2.next=null, prev=2, curr=3 （2→null）
第二次：next=4, 3.next=2, prev=3, curr=4 （3→2→null）
第三次：next=5, 4.next=3, prev=4, curr=5 （4→3→2→null）
结束：prev=4（新头）, curr=5（suc_right）
连接：pre_left(1).next = 4, left_node(2).next = 5
得到：1→4→3→2→5
返回 dummy.next = 节点1

时间复杂度：O(n)，只需一趟扫描。
空间复杂度：O(1)，只使用了常数个额外指针。

反转链表 II（LeetCode 92）题目描述：给你单链表的头指针 head 和两个整数 left 和 right，其中 left ≤ right。请你反转从位置 left 到位置 right 的链表节点，并返回反转后的链表。要求：只使用一趟扫描完成反转。示例：输入：head = [ 1,2,3,4,5 ], left = 2, right = 4 输出：[ 1,4,3,2,5 ] 解释：原始链表 1→2→3→4→5，反转位置 2 到 4 的节点后变为 1→4→3→2→5。解题步骤：这是一个在单链表中反转指定区间的经典问题，我们可以用“头插法”的思想在一趟扫描中完成。创建哑结点（dummy node）为了方便处理 left=1 的情况（即从头节点开始反转），我们在原链表头部前添加一个哑结点 dummy，dummy.next = head。这样所有节点都有一个统一的前驱，不需要特殊处理头节点变化。定位关键节点我们需要找到四个关键位置： pre_ left：要反转区间的前一个节点，最终用于连接反转后的新头。 left_ node：要反转区间的第一个节点。 right_ node：要反转区间的最后一个节点。 suc_ right：要反转区间的后一个节点，最终用于连接反转后的剩余链表。由于 left 和 right 可能很大，我们通过指针移动来定位，而不是用数组存储。第一步：找到 pre_ left 和 left_ node 从 dummy 开始，向前移动 left-1 步，即可到达 pre_ left。然后 left_ node = pre_ left.next。注意：如果 left=1，pre_ left 就是 dummy，left_ node 就是原 head。第二步：反转区间 [ left, right] 的链表从 left_ node 开始，到 right_ node 结束，我们需要反转这个子链表。使用三个指针进行反转： prev = null（反转后的新头） curr = left_ node（当前要处理的节点） for 循环执行 (right-left+1) 次，即区间长度次迭代。在每次循环中： a. 保存下一个节点：next_ node = curr.next b. 反转指针：curr.next = prev c. 更新指针：prev = curr, curr = next_ node 循环结束后： prev 指向反转后的新头，即原 right_ node。 curr 指向 suc_ right，即原 right_ node 的下一个节点。此时，子链表已经独立反转，但还未与前后部分连接。第三步：重新连接链表现在我们有： pre_ left 指向 left_ node 的前一个节点。 left_ node 现在是反转后的最后一个节点（因为它是原子链表的第一个节点，反转后变成最后一个）。 prev 是反转后的新头（原 right_ node）。 curr 是 suc_ right（原 right_ node 的下一个节点）。连接步骤： a. 将 pre_ left.next 指向 prev（新头）。 b. 将 left_ node.next 指向 curr（剩余链表）。这样整个链表就重新连接好了。返回结果最终返回 dummy.next，即新链表的头节点。示例推演（head = [ 1,2,3,4,5 ], left=2, right=4）：初始：dummy(0)→1→2→3→4→5 定位：pre_ left = 节点1, left_ node = 节点2 反转区间：初始：prev=null, curr=2 第一次：next=3, 2.next=null, prev=2, curr=3 （2→null）第二次：next=4, 3.next=2, prev=3, curr=4 （3→2→null）第三次：next=5, 4.next=3, prev=4, curr=5 （4→3→2→null）结束：prev=4（新头）, curr=5（suc_ right）连接：pre_ left(1).next = 4, left_ node(2).next = 5 得到：1→4→3→2→5 返回 dummy.next = 节点1 时间复杂度：O(n)，只需一趟扫描。空间复杂度：O(1)，只使用了常数个额外指针。