旋转链表 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你一个链表的头节点 head，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1

输入：head = [1,2,3,4,5], k = 2

输出：[4,5,1,2,3]

示例 2

输入：head = [0,1,2], k = 4

输出：[2,0,1]

💭 模拟答题者思考

1. 最直接：把每个节点向右移 k 次，每次把尾节点摘下来插到头部——能过但 O(n·k)，k 可达 2×10⁹ 会超时。

2. 重复在哪里？右移 k 步等价于「最后 k 个节点整体搬到前面」；若链表长为 n，实际只需旋转 k % n 步，k ≥ n 时效果与 k % n 相同（示例 2：k=4, n=3 → 有效 k=1）。

3. 关键观察：新头是原链表中正数第 n-k+1 个节点（0-indexed 为第 n-k 个）。例如 [1,2,3,4,5], k=2：新头为 4，即走 5-2=3 步。

4. 成环技巧：把 tail.next = head 连成环后，从 head 走 n-k 步即到新头；新尾是新头的前驱，断环 new_tail.next = None 即可。

5. 与 #19「删除倒数第 N 个」对比：#19 用双指针间距定位节点，本题用「先数长度、再成环一次定位」——都是 O(n) 一遍或两遍，核心都是利用长度信息避免重复遍历。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`n`	int	定义：链表节点总数维护：一遍遍历从 1 累加到尾节点，同时记录 `tail` 更新：遍历结束后只读；用于 `k %= n` 和定位新头位置 `n - k`
`tail`	ListNode*	定义：原链表的最后一个节点维护：遍历时 `cur` 每次前进，最终停在末尾更新：执行 `tail.next = head` 把链表首尾相接成环，为「一次走到新头」创造条件
`k`	int	定义：题面给出的右移步数维护：先 `k %= n` 取有效旋转量；若 `k == 0` 则无需旋转更新：有效步数决定新头在环上距原头 `n - k` 步的位置
`cur`	ListNode*	定义：环上行走指针，初始为 `head` 维护：从原头出发，在成环后向前走 `n - k` 步更新：停下时 `cur` 即为新头 `new_head`；其前驱 `new_tail` 负责断环
`new_tail`	ListNode*	定义：旋转后新链表的尾节点，即新头的前驱维护：在环上走到 `new_head` 的前一个节点（走 `n - k - 1` 步）更新：执行 `new_tail.next = None` 断开环，返回 `new_head`

⌨️ 落码步骤

1. 若 head 为空或只有一个节点，直接返回

2. 一遍遍历：统计长度 n，记录尾节点 tail

3. 有效旋转量：k %= n；若 k == 0 返回 head

4. 成环：tail.next = head

5. 从 head 走 n - k - 1 步得到 new_tail

6. new_head = new_tail.next，断环 new_tail.next = None

7. 返回 new_head

💻 代码实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # 统计长度并找到尾节点
        n = 1
        tail = head
        while tail.next:
            tail = tail.next
            n += 1

        k %= n
        if k == 0:
            return head

        # 成环，定位新尾（新头的前驱）
        tail.next = head
        cur = head
        for _ in range(n - k - 1):
            cur = cur.next

        new_head = cur.next
        cur.next = None  # 断环
        return new_head

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next) return head;

        int n = 1;
        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
            n++;
        }

        k %= n;
        if (k == 0) return head;

        tail->next = head;  // 成环
        ListNode* cur = head;
        for (int i = 0; i < n - k - 1; i++)
            cur = cur->next;

        ListNode* newHead = cur->next;
        cur->next = nullptr;  // 断环
        return newHead;
    }
};
// 时间 O(n)，空间 O(1)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(1)

⚠️ 常见坑

❗ 忘记 k %= n：k 可达 2×10⁹，且 k ≥ n 时旋转等价于 k % n（如 k=4, n=3 只需转 1 步）。

❗ k == 0 时未提前返回：有效旋转量为 0 时链表不变，无需成环断环，直接返回 head。

❗ 走路步数错误：新尾在环上距原头 n - k - 1 步（不是 n - k 或 k），走多了新头会错位。

🔍 必测边界 Case

Case 1：k 大于链表长度

head = [0,1,2], k = 4 → [2,0,1]（4 % 3 = 1，等价于右移 1 步）

Case 2：k 为 0 或 n 的倍数

head = [1,2,3], k = 3 → [1,2,3]（3 % 3 = 0，链表不变）

Case 3：空链表 / 单节点

head = [], k = 0 → []；head = [1], k = 5 → [1]

Case 4：k = 1（最小有效旋转）

head = [1,2,3,4,5], k = 1 → [5,1,2,3,4]（尾节点 5 移到头部）

Case 5：k = n - 1（几乎全部旋转）

head = [1,2,3,4,5], k = 4 → [2,3,4,5,1]（仅首节点移到末尾）