0061. Rotate List¶
题目信息¶
- 题号:
旋转链表
- 难度:
Medium
- 主题:
链表、双指针、模运算
- 原题:
- 重点:
从逐次移动尾节点,推导到确定唯一切口并通过成环断开完成旋转
题目重述¶
给定单链表 head 和非负整数 k,把链表向右旋转 k 次并返回新的头节点。
一次右旋会把当前尾节点移动到链表最前方。例如:
1 -> 2 -> 3 -> 4
右旋一次后变为:
4 -> 1 -> 2 -> 3
链表节点数在 0..500 范围内,节点值在 -100..100 范围内,0 <= k <= 2 * 10^9。
自建示例¶
输入:1 -> 2 -> 3 -> 4 -> 5 -> 6,k = 8
输出:5 -> 6 -> 1 -> 2 -> 3 -> 4
链表长度为 6,8 % 6 = 2,因此只需把最后两个节点整体移到前面。
输入:7 -> 8 -> 9,k = 6
输出:7 -> 8 -> 9
6 % 3 = 0,完整旋转两圈后顺序不变。
输入:空链表,k = 5
输出:空链表
空链表没有可移动节点,直接返回空指针。
C++ 实现¶
class Solution {
private:
ListNode* moveTailToFrontRepeatedly(ListNode* head, int k) {
if (!head || !head->next) return head;
while (k-- > 0) {
ListNode* previous = nullptr;
ListNode* tail = head;
while (tail->next) {
previous = tail;
tail = tail->next;
}
previous->next = nullptr;
tail->next = head;
head = tail;
}
return head;
}
ListNode* splitAndReconnect(ListNode* head, int k) {
if (!head || !head->next) return head;
int length = 0;
for (ListNode* node = head; node; node = node->next) {
++length;
}
int shift = k % length;
if (shift == 0) return head;
ListNode* fast = head;
for (int step = 0; step < shift; ++step) {
fast = fast->next;
}
ListNode* slow = head;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
ListNode* newHead = slow->next;
slow->next = nullptr;
fast->next = head;
return newHead;
}
ListNode* makeCycleAndCut(ListNode* head, int k) {
if (!head || !head->next) return head;
int length = 1;
ListNode* tail = head;
while (tail->next) {
tail = tail->next;
++length;
}
int shift = k % length;
if (shift == 0) return head;
tail->next = head;
int stepsToNewTail = length - shift - 1;
ListNode* newTail = head;
while (stepsToNewTail-- > 0) {
newTail = newTail->next;
}
ListNode* newHead = newTail->next;
newTail->next = nullptr;
return newHead;
}
public:
ListNode* rotateRight(ListNode* head, int k) {
return makeCycleAndCut(head, k);
}
};
题解¶
逐次右移基线¶
一次右旋可以直接按定义完成:扫描到尾节点并记录其前驱,摘下尾节点,再把它接到旧头之前。
moveTailToFrontRepeatedly 重复该过程 k 次,每次扫描需要 O(n),总时间最坏为
O(kn)。当 k 接近 2 * 10^9 时,瓶颈来自对同一链表的反复遍历。
旋转周期压缩¶
长度为 n 的链表右旋 n 次后,每个节点都会回到原位置,因此只有余数会改变结果:
shift = k % n
取模前必须先排除空链表;单节点链表也可以直接返回。若 shift == 0,结果与原链表相同,不需要修改
任何指针。
唯一切口¶
有效右移量为 shift 时,原链表可以分成两段:
A 长度为 n - shift
B 长度为 shift
原顺序:A -> B
新顺序:B -> A
所以旋转只需要找到 A 的最后一个节点。按零基下标计算,新尾位于:
n - shift - 1
它的下一个节点就是新头。重复移动尾节点的过程,等价于一次把后缀 B 整体移到前面。
双指针切分¶
splitAndReconnect 让 fast 先走 shift 步,再让 fast 和 slow 同步前进,直到
fast 到达旧尾。此时 slow 后面恰好剩下 shift 个节点,因此 slow 就是新尾。
保存 slow->next 作为新头后,先断开旧前缀,再令旧尾连接旧头,即可得到 B -> A。该方法无需显式
计算新尾下标,但仍需先统计长度以完成取模。
成环后断开¶
主方法先在统计长度时保留旧尾,再令:
tail->next = head
全部节点暂时构成一个环。环上没有固定起点,因此旋转不再需要“移动”节点,只需在正确位置重新断开。
找到下标 n - shift - 1 处的新尾后:
newHead = newTail->next
newTail->next = nullptr
旧尾已经通过环连接到旧头,所以这一次断开同时确定新头和新尾,完成全部重连。
旋转切口不变量¶
统计长度后,tail 指向原链表最后一个节点,length 是节点总数。成环不会创建或删除节点,只新增
tail -> head 这一条边。
从旧头向前走 length - shift - 1 步到达新尾,说明它前面保留 length - shift 个节点,后面保留
shift 个节点。断开 newTail->next 后,环重新变成一条包含全部节点的单链表,起点正是原后缀的首节点。
必须先保存 newHead = newTail->next 再断开。若先断开,会丢失新头入口;若成环后不再断开,返回结果将
是循环链表。
状态演化¶
以 1 -> 2 -> 3 -> 4 -> 5、k = 2 为例:
阶段 |
状态 |
含义 |
|---|---|---|
统计长度 |
|
旧尾是节点 5 |
计算位移 |
|
最后两个节点移到前面 |
临时成环 |
|
所有节点进入同一个环 |
定位新尾 |
下标 |
节点 4 将成为新头 |
断开 |
|
得到 |
三种方法的关系¶
逐次右移真实执行每一次旋转;双指针法一次定位后缀起点;成环法进一步把“断开再拼接”压缩为“先连接旧尾,
再在新尾处断开”。三种方法产生相同切口,主入口调用指针关系最集中的 makeCycleAndCut。
复杂度分析¶
逐次右移方法最坏为 O(kn) 时间。双指针法和成环法都只进行常数次链表扫描,时间为 O(n),额外空间
为 O(1)。
任何方法在最坏情况下都必须到达旧尾,才能确定长度与旋转切口,因此需要 Ω(n) 时间;主方法达到该下界。