0061. Rotate List

题目信息

题号:
  1. 旋转链表

难度:

Medium

主题:

链表、双指针、模运算

原题:

LeetCode 0061

重点:

从逐次移动尾节点,推导到确定唯一切口并通过成环断开完成旋转

题目重述

给定单链表 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 为例:

阶段

状态

含义

统计长度

length = 5

旧尾是节点 5

计算位移

shift = 2

最后两个节点移到前面

临时成环

5.next = 1

所有节点进入同一个环

定位新尾

下标 5 - 2 - 1 = 2,节点 3

节点 4 将成为新头

断开

3.next = nullptr

得到 4 -> 5 -> 1 -> 2 -> 3

三种方法的关系

逐次右移真实执行每一次旋转;双指针法一次定位后缀起点;成环法进一步把“断开再拼接”压缩为“先连接旧尾, 再在新尾处断开”。三种方法产生相同切口,主入口调用指针关系最集中的 makeCycleAndCut。

复杂度分析

逐次右移方法最坏为 O(kn) 时间。双指针法和成环法都只进行常数次链表扫描,时间为 O(n),额外空间 为 O(1)。

任何方法在最坏情况下都必须到达旧尾,才能确定长度与旋转切口,因此需要 Ω(n) 时间;主方法达到该下界。