LeetCode Rotate List：鏈表循環右移 K 位

問題描述

給定單鏈表頭節點，將鏈表向右循環移動 k 位。如 1→2→3→4→5, k=2 → 4→5→1→2→3。k 可能大於鏈表長度。

解題思路

1. 遍歷鏈表得長度 n，並記錄尾節點 tail。
2. k = k % n；若 k==0 直接返回頭節點。
3. 找到新頭節點的前驅：即第 n-k 個節點（0-indexed 為 n-k-1）。
4. 新頭 = 前驅->next；前驅->next = null；tail->next = 老頭；返回新頭。

代碼實現 (C++)

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head;
        int len = 1;
        ListNode* tail = head;
        while (tail->next) { tail = tail->next; ++len; }
        k %= len;
        if (k == 0) return head;
        ListNode* prev = head;
        for (int i = 0; i < len - k - 1; ++i) prev = prev->next;
        ListNode* newHead = prev->next;
        prev->next = nullptr;
        tail->next = head;
        return newHead;
    }
};

複雜度分析

• 時間複雜度：O(n)。
• 空間複雜度：O(1)。

總結

鏈表循環右移本質是斷開重連，關鍵在於找到斷開點。先成環再斷開也是常見技巧（tail->next = head，然後移動 n-k 步斷開）。