0092. Reverse Linked List II¶
题目信息¶
- 题号:
反转链表 II
- 难度:
Medium
- 主题:
单链表、区间反转、哨兵节点
- 原题:
- 重点:
从保存节点顺序,推导到固定区间前驱并原地完成局部反转
题目重述¶
给定单链表 head 和两个一基位置 left、right,反转第 left 个节点到第
right 个节点组成的闭区间,并返回反转后的链表。
区间外节点的相对顺序必须保持不变。链表节点数为 1..500,并保证
1 <= left <= right <= 链表长度。附加要求是尽量只遍历链表一次。
自建示例¶
输入:9 -> 8 -> 7 -> 6 -> 5,left = 2,right = 5
输出:9 -> 5 -> 6 -> 7 -> 8
第 2 到第 5 个节点整体逆序,首节点 9 保持原位。
输入:1 -> 2 -> 3 -> 4,left = 1,right = 3
输出:3 -> 2 -> 1 -> 4
反转区间从头节点开始,因此结果链表的头节点发生变化。
输入:3 -> 4 -> 5,left = 2,right = 2
输出:3 -> 4 -> 5
区间长度为 1 时,不需要移动任何节点。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
ListNode* nodeArray(ListNode* head, int left, int right) {
std::vector<ListNode*> nodes;
for (ListNode* node = head; node; node = node->next) {
nodes.push_back(node);
}
std::reverse(nodes.begin() + left - 1, nodes.begin() + right);
for (int index = 0; index + 1 < static_cast<int>(nodes.size()); ++index) {
nodes[index]->next = nodes[index + 1];
}
nodes.back()->next = nullptr;
return nodes.front();
}
ListNode* reverseAndReconnect(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* before = &dummy;
for (int position = 1; position < left; ++position) {
before = before->next;
}
ListNode* segment_tail = before->next;
ListNode* current = segment_tail;
ListNode* previous = nullptr;
for (int count = 0; count <= right - left; ++count) {
ListNode* next = current->next;
current->next = previous;
previous = current;
current = next;
}
before->next = previous;
segment_tail->next = current;
return dummy.next;
}
ListNode* frontInsertion(ListNode* head, int left, int right) {
ListNode dummy(0, head);
ListNode* before = &dummy;
for (int position = 1; position < left; ++position) {
before = before->next;
}
ListNode* segment_tail = before->next;
for (int step = 0; step < right - left; ++step) {
ListNode* moved = segment_tail->next;
segment_tail->next = moved->next;
moved->next = before->next;
before->next = moved;
}
return dummy.next;
}
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
return frontInsertion(head, left, right);
}
};
题解¶
节点顺序重排¶
最直接的方法是把所有节点地址保存到数组中,反转下标区间 [left-1, right),再按数组顺序重建
next 链接。它把链表问题转成数组区间反转,逻辑直观,额外空间为 O(n)。
链表本身已经提供了全部节点,继续寻找不保存数组的原地做法。
区间的三处连接¶
设 before 是第 left 个节点的前驱。局部反转完成后只需保证三部分正确相接:
原前缀尾 before
|
v
反转后的区间头 ... 原区间首节点 segment_tail -> 原后缀头
当 left = 1 时不存在真实前驱。令 dummy.next = head,则 before 始终存在,结果头节点也统一从
dummy.next 返回。
标准局部反转¶
从 before.next 开始执行普通链表反转,恰好处理 right-left+1 个节点。循环结束时:
previous指向反转后的区间头;segment_tail是原区间首节点,也是反转后的区间尾;current指向原第right个节点之后的后缀头。
因此只需执行:
before.next = previous
segment_tail.next = current
这种方法先完成整段指针翻转,再恢复区间两端连接。
头插法的局部状态¶
还可以固定 before 与 segment_tail,反复把 segment_tail 后面的节点摘出并插到区间最前面:
moved = segment_tail.next
segment_tail.next = moved.next
moved.next = before.next
before.next = moved
每轮开始时,before.next 是当前已反转部分的头,segment_tail 是其尾,
segment_tail.next 是下一个尚未移动的区间节点。
状态演化¶
以 1 -> 2 -> 3 -> 4 -> 5、left=2、right=4 为例:
阶段 |
链表 |
下一步移动 |
|---|---|---|
初始 |
|
3 |
第一次 |
|
4 |
第二次 |
|
完成 |
区间共有 right-left+1 个节点。原首节点已经位于局部结构中,其余 right-left 个节点各执行一次
头插,整段便完成逆序。
连接安全性¶
摘出 moved 时先令 segment_tail.next = moved.next,保留未处理区间和后缀;随后再把 moved
接到 before 后面。任何时刻每个节点都只有一个前驱路径,不会丢失节点或形成环。
before 之前和最终后缀内部的链接从未改变,所以区间外节点的相对顺序保持不变。每个原节点也只被移动或保留一次,
结果中的节点集合与输入完全相同。
复杂度¶
节点数组方法时间 O(n)、额外空间 O(n)。标准局部反转和头插法都只定位一次区间前驱,并处理
区间内节点一次,时间 O(n)、额外空间 O(1)。