旋转链表 图解题解

这道题到底在问什么

输入

1 → 2 → 3 → 4 → 5, k = 2

输出

4 → 5 → 1 → 2 → 3

最优解：一步一步想明白

1. 3最直觉的做法：每次把尾节点摘下来接到头前，重复 k 次。可 k 能大到上亿，挪 k 次会超时。而且旋转 n 次就回到原样——挪 k 次其实等于挪 k 除以 n 的余数次。我们要更聪明的一刀法。
2. 4① 走到尾节点、顺便数出长度 n，把尾接回头形成环；② 真正生效的旋转量是 k 余 n，新的尾节点在第 n−k 个位置；③ 从头走 n−k−1 步停在新尾，它的下一个就是新头，最后把环在这里剪断。下面用 1→2→3→4→5、k=2 慢放。
3. 5n=1，tail=1tail 从头节点 1 出发，计数 n 从 1 起步。一边走到链尾、一边把节点数出来。
4. 6tail=5，n=5tail 一路走到 5，它的 next 是 null，停。此时 n=5——链表一共 5 个节点。
5. 7k = 2 % 5 = 2先给 k 取模：k = 2 % 5 = 2。如果 k 比 n 大，转一整圈白转，余数才是真正要挪的量。这里余数还是 2。
6. 85 → 1，连成环执行 tail.next = head：把尾节点 5 接回头节点 1（图上 5 多出一根箭头绕回 1），整条链闭合成环。现在没有头也没有尾，转圈不会掉出去。
7. 9steps = 5−2−1 = 2新的尾节点在第 n−k = 3 个位置（节点 3）。从头节点 1 出发，再走 n−k−1 = 2 步就能停在它身上。cur 现在站在起点 1。
8. 10cur = 2（剩 1 步）cur 走一步到节点 2。还差 1 步到新尾。
9. 11cur = 3 ← 新尾cur 再走一步到节点 3，走满 2 步。这就是新的尾节点——它后面那个 4 将成为新头。
10. 123 ✕→ ，新头 = 4记下新头 new_head = 3 的 next = 4，再执行 3.next = None 把环剪断。沿着新头 4 读出来：4 → 5 → 1 → 2 → 3 → null，正是答案。
11. 15旋转的本质就是换一个起点。接环后整条链是一个圈，从哪剪开、哪就是新头——新头在第 n−k+1 个位置（节点 4），新尾在它前一个（节点 3）。
12. 17k=7 ＞ n=5：必须取模若 k=7：转 5 次回原点，多出的 7−5=2 次才有效。7 % 5 = 2，结果和 k=2 完全一样。不取模就会让 new_tail 越过尾、走进环里出不来。这就是为什么第一步必须 k %= n。
13. 21「数长度 + 找第 m 个节点 + 在某处断开重接」是一整类链表题的原子操作：LC19 删倒数第 N 个（先定位）、LC24 两两交换、LC25 K 个一组翻转都靠它。学会这一道，链表的切割重组就通了——更多在 链表专题 继续，不懂可随时问右下角的 AI 助教小欧。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def rotateRight(self, head, k):
        if not head or not head.next or k == 0:
            return head
        n, tail = 1, head
        while tail.next:        # 走到尾，数出长度 n
            tail = tail.next
            n += 1
        k %= n                  # 有效旋转量
        if k == 0:
            return head         # 整圈，原样返回
        tail.next = head        # ① 接成环
        new_tail = head
        for _ in range(n - k - 1):  # ② 走到新尾
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None    # ③ 断开
        return new_head

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) 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* newTail = head;
        for (int i = 0; i < n - k - 1; i++)  // ② 走到新尾
            newTail = newTail->next;
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;   // ③ 断开
        return newHead;
    }
};

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int n = 1;
        ListNode tail = head;
        while (tail.next != null) {  // 走到尾，数长度
            tail = tail.next;
            n++;
        }
        k %= n;                     // 有效旋转量
        if (k == 0) return head;
        tail.next = head;           // ① 接成环
        ListNode newTail = head;
        for (int i = 0; i < n - k - 1; i++)  // ② 走到新尾
            newTail = newTail.next;
        ListNode newHead = newTail.next;
        newTail.next = null;        // ③ 断开
        return newHead;
    }
}

# 凡是「整体平移 / 在第 m 个节点处切割」的链表题都套
n, tail = 1, head
while tail.next:          # 一趟走到尾，顺便数长度
    tail = tail.next; n += 1
k %= n                    # 有效偏移，去掉整圈
# tail.next = head        # 需要环就接上（旋转题用）
node = head
for _ in range(?):        # 走到目标断点（步数按题推）
    node = node.next
# ... 在 node 处切割 / 断开 / 重接 ...

int n = 1; ListNode* tail = head;
while (tail->next) { tail = tail->next; n++; }  // 数长度
k %= n;                       // 有效偏移
// tail->next = head;         // 需要环就接（旋转题）
ListNode* node = head;
for (int i = 0; i < ?; i++)   // 走到断点
    node = node->next;
// ... 在 node 处切割 / 断开 / 重接 ...

int n = 1; ListNode tail = head;
while (tail.next != null) { tail = tail.next; n++; }  // 数长度
k %= n;                       // 有效偏移
// tail.next = head;          // 需要环就接（旋转题）
ListNode node = head;
for (int i = 0; i < ?; i++)   // 走到断点
    node = node.next;
// ... 在 node 处切割 / 断开 / 重接 ...

复杂度

面试官可能追问