61. Rotate List

題目 / Problem

中文： 給定一個鏈結串列的頭節點 head，把整個串列向右旋轉 k 個位置。所謂「向右旋轉一次」，就是把最後一個節點搬到最前面。旋轉 k 次後回傳新的頭節點。

English: Given the head of a linked list, rotate the list to the right by k places. "Rotating right once" means taking the last node and moving it to the front. After doing this k times, return the new head.

Constraints / 限制： - 節點數量範圍 [0, 500] / The number of nodes is in the range [0, 500]. - -100 <= Node.val <= 100 - 0 <= k <= 2 * 10^9（注意 k 可以非常大 / note k can be huge）

Worked example / 範例：

Input:  head = [1,2,3,4,5], k = 2
Output: [4,5,1,2,3]

把最後 2 個節點 4,5 整段搬到最前面。/ The last 2 nodes 4,5 move to the front as a block.

名詞解釋 / Glossary

• 鏈結串列 / linked list：一串節點（node），每個節點存一個值 val 和一個指向下一個節點的指標 next。最後一個節點的 next 是 NULL（空）。你只能從頭開始一個一個往後走，不能像陣列那樣直接跳到第 5 個。/ A chain of nodes; each node holds a value and a pointer to the next node. The last node points to NULL. You can only walk forward one step at a time.
• 指標 / pointer：一個「記住某節點位址」的變數。p = p->next 就是讓 p 往後移一格。/ A variable that remembers where a node lives in memory. p = p->next moves p one node forward.
• 環狀串列 / circular list：把最後一個節點的 next 接回頭節點，形成一個圈。這是本題的關鍵技巧。/ Connect the last node's next back to the head, forming a loop — the key trick here.
• 取餘數 / modulo (%)：k % n 得到 k 除以 n 的餘數。因為旋轉 n 次（n 是長度）會回到原狀，所以只有 k % n 才是「真正有效的旋轉量」。/ k % n is the remainder. Rotating a full length n returns to the original, so only k % n actually matters.
• 雙指針 / two pointers：用兩個指標一前一後或一快一慢來定位節點，這裡用來一次走到「新的尾巴」和「新的頭」。/ Using two pointers to locate positions in one pass.

思路

最直覺的暴力法是：真的旋轉 k 次，每次把最後一個節點搬到最前面。但 k 最大可以到 2 × 10^9，一次一次搬會慢到超時。而且我們馬上會發現一個規律：假設串列長度是 n，旋轉 n 次之後串列會完全回到原樣。所以旋轉 k 次和旋轉 k % n 次的結果一模一樣。這一步先把巨大的 k 縮小成 0 到 n-1 之間的數字。接著觀察旋轉的本質：向右旋轉 k（已取餘數）次，等於把串列從「倒數第 k 個節點的前面」切斷，把後半段接到前半段前面。所以真正的新頭是「倒數第 k 個節點」，新的尾巴是「倒數第 k+1 個節點」。最乾淨的做法是：先走一遍算出長度 n，順便走到舊的尾巴；把舊尾巴的 next 接回舊頭，形成一個環；然後從舊頭往前走 n - k % n 步，走到新尾巴的位置，把它的 next 斷開設成 NULL，它的下一個節點就是新頭。整個過程只走兩趟串列，時間是線性的。

The brute-force idea is to literally rotate k times, each time moving the last node to the front. But k can be as large as 2 × 10^9, so one-at-a-time is far too slow. The key insight: if the list has length n, rotating n times brings it back to the original arrangement. Therefore rotating k times gives the same result as rotating k % n times — this instantly shrinks a giant k down to a number between 0 and n-1. Next, notice what a right-rotation really does: it cuts the list k nodes from the end and moves that tail block to the front. So the new head is the node that is k positions from the end, and the new tail is the node just before it. The cleanest implementation: walk once to compute the length n and reach the old tail; connect the old tail's next back to the old head to form a circular list; then walk n - k % n steps forward from the old head to land on the new tail; break the circle there by setting its next to NULL. The node right after that break is the new head. This touches the list only twice, so it runs in linear time.

逐步走查 / Walkthrough

Example: head = [1,2,3,4,5], k = 2.

Step 1 — 算長度並找舊尾巴 / Count length, find old tail:

So n = 5, old tail is node 5.

Step 2 — 縮小 k / Reduce k: k % n = 2 % 5 = 2. 有效旋轉量是 2。/ Effective rotation is 2.

Step 3 — 接成環 / Make it circular: 把節點 5 的 next 指回節點 1。現在 1→2→3→4→5→1→...。/ Node 5's next now points to node 1.

Step 4 — 走到新尾巴 / Walk to the new tail: 要走 n - k = 5 - 2 = 3 步，從舊頭 1 出發。/ Walk n - k = 3 steps from old head 1.

Step 5 — 斷環 / Break the circle: 新頭是新尾巴的下一個 = 節點 4->next = 節點 5。把節點 4 的 next 設為 NULL。/ New head is newTail->next = node 5; set node 4's next to NULL.

Result / 結果: 5 → 4? 等一下，新頭是節點 5，串列變成 5,4,...？ Let's read the circle from the new head 4... actually new head = node after node 4 = node 5, giving 5,1,2,3? Re-trace: circle is 1→2→3→4→5→1. New tail is node 4, so break after 4: chain from new head = 5→1→2→3→4(→NULL) = [5,1,2,3,4].

Hmm, that gives [5,1,2,3,4], but expected is [4,5,1,2,3]. The walk count must be n - k where we stop on the new tail. Let me recount: new tail should be node 3 (倒數第 3 個 = the (n-k)-th node counting from head, 1-indexed). Walk n - k - 1 = 2 steps from head lands on node 3. Break after 3: new head = node 4, chain = 4→5→1→2→3(→NULL) = [4,5,1,2,3] ✓.

重點 / Key: from the old head, take n - k - 1 steps (2 steps) to reach the new tail (node 3). The code below moves a pointer steps = n - k % n - 1 times. / 從舊頭走 n - k%n - 1 步到達新尾巴。

Solution — C

/*
 * 演算法 / Algorithm:
 * 1) 走一遍算長度 n，並找到舊尾巴。/ Walk once to get length n and the old tail.
 * 2) k %= n 縮小旋轉量；把尾巴接回頭形成環。/ Reduce k, connect tail->head into a circle.
 * 3) 從頭走 (n - k - 1) 步到新尾巴，斷環，回傳新頭。
 *    / Walk (n - k - 1) steps to the new tail, break the circle, return new head.
 */

// LeetCode 提供的節點定義 / Node definition provided by LeetCode:
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* rotateRight(struct ListNode* head, int k) {
    // 空串列或只有一個節點：旋轉後不變，直接回傳。
    // Empty or single-node list: rotation changes nothing, return as-is.
    if (head == NULL || head->next == NULL) return head;

    // ---- 第一趟：算長度 n，同時把 tail 停在最後一個節點 ----
    // ---- Pass 1: count length n, leave tail on the last node ----
    int n = 1;                          // 已經有 head 這一個節點 / head itself counts as 1
    struct ListNode* tail = head;       // tail 從頭開始往後走 / start walking from head
    while (tail->next != NULL) {        // 只要還有下一個節點就繼續 / while a next node exists
        tail = tail->next;              // 往後移一格 / step forward one node
        n++;                            // 長度加一 / length grows by one
    }
    // 迴圈結束後 tail 指向最後一個節點，n 是總長度。
    // After the loop, tail is the last node and n is the total length.

    // ---- 縮小 k：旋轉 n 次會回到原狀，所以只有餘數有意義 ----
    // ---- Reduce k: rotating n times is a no-op, only the remainder matters ----
    k = k % n;                          // 例如 k=2, n=5 -> k=2 / e.g. k becomes 2
    if (k == 0) return head;            // 沒有實際旋轉，直接回傳 / nothing to rotate

    // ---- 接成環：舊尾巴指回舊頭 ----
    // ---- Make it circular: old tail points back to old head ----
    tail->next = head;                  // 現在是 1->2->3->4->5->1->... / now it loops

    // ---- 找新尾巴：從頭走 (n - k - 1) 步 ----
    // ---- Find new tail: walk (n - k - 1) steps from head ----
    int stepsToNewTail = n - k - 1;     // 新尾巴是第 (n-k) 個節點(1-indexed) / the (n-k)-th node
    struct ListNode* newTail = head;    // 從頭出發 / start from head
    for (int i = 0; i < stepsToNewTail; i++) {  // 走指定步數 / take that many steps
        newTail = newTail->next;        // 每次前進一格 / advance one node each time
    }

    // ---- 斷環：新頭是新尾巴的下一個節點 ----
    // ---- Break the circle: new head is the node right after new tail ----
    struct ListNode* newHead = newTail->next;  // 記住新頭 / remember the new head
    newTail->next = NULL;               // 切斷，讓新尾巴成為真正的結尾 / cut, making it the real end

    return newHead;                     // 回傳旋轉後的頭節點 / return the rotated head
}

Solution — C++

/*
 * 演算法 / Algorithm (與 C 版相同 / same as the C version):
 * 走一遍算長度並找尾巴 -> k %= n -> 接成環 -> 走 (n-k-1) 步找新尾巴 -> 斷環回傳新頭。
 * Count length + find tail -> reduce k -> circularize -> walk (n-k-1) steps -> break, return new head.
 */

// LeetCode 提供的節點定義 / Node definition provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        // 空串列或單一節點：旋轉不改變任何東西。
        // Empty or single node: rotation is a no-op.
        if (head == nullptr || head->next == nullptr) return head;

        // ---- 第一趟：算長度 n，tail 停在最後一個節點 ----
        // ---- Pass 1: compute length n; tail ends on the last node ----
        int n = 1;                       // head 本身算一個 / head counts as one
        ListNode* tail = head;           // 從頭開始走 / start at head
        while (tail->next != nullptr) {  // 還有下一個就繼續 / while a next node exists
            tail = tail->next;           // 前進一格 / move forward
            ++n;                         // 長度加一 / increase length
        }

        // ---- 縮小 k：只有 k % n 有意義 ----
        // ---- Reduce k: only k % n matters ----
        k %= n;                          // 等同 k = k % n / same as k = k % n
        if (k == 0) return head;         // 沒有實際旋轉 / no real rotation needed

        // ---- 接成環 ----
        // ---- Make it circular ----
        tail->next = head;               // 尾巴接回頭 / last node loops back to head

        // ---- 走 (n - k - 1) 步找新尾巴 ----
        // ---- Walk (n - k - 1) steps to reach the new tail ----
        ListNode* newTail = head;        // 從頭出發 / start from head
        for (int i = 0; i < n - k - 1; ++i) {  // 走固定步數 / take fixed number of steps
            newTail = newTail->next;     // 每次前進一格 / advance one node
        }

        // ---- 斷環，取得新頭 ----
        // ---- Break the circle, get the new head ----
        ListNode* newHead = newTail->next;  // 新尾巴的下一個就是新頭 / node after new tail is the new head
        newTail->next = nullptr;         // 切斷環，成為真正結尾 / cut the loop to make a proper end

        return newHead;                  // 回傳新頭 / return the rotated head
    }
};

複雜度 / Complexity

• Time: O(n) — 我們最多把串列走兩趟：一趟算長度、一趟走到新尾巴（n - k - 1 步 ≤ n）。n 是節點數。取餘數 k % n 是 O(1)，所以總和仍是線性。/ We traverse the list at most twice — once to count, once to reach the new tail. n is the number of nodes; k % n is O(1), so the total is linear.
• Space: O(1) — 只用了幾個指標變數（tail、newTail、newHead）和一個整數 n，沒有額外配置和輸入大小相關的記憶體。/ Only a few pointer variables and one integer are used; no extra memory that grows with input size.

Pitfalls & Edge Cases

• k 非常大 / Huge k：k 可達 2 × 10^9，若真的旋轉 k 次會超時。務必先 k %= n 把它縮到 [0, n-1]。/ Always reduce with k %= n first, or you'll time out (and looping k times is pointless).
• 忘記取餘數導致越界 / Forgetting modulo causes over-walking：若不縮小 k，n - k - 1 可能變成很大的負數，迴圈行為錯誤。取餘數後 k < n，步數必為 0..n-2，安全。/ Without reducing k, n - k - 1 can go wildly negative; after modulo the step count is always valid.
• k % n == 0 的情況 / When k % n == 0：此時旋轉後串列不變，要提早回傳原 head。若不處理，接成環後又走到原尾巴，雖然通常仍正確，但提早回傳更清楚也避免無謂操作。/ If the effective rotation is zero, return the original head early — cleaner and avoids needless work.
• 空串列或單節點 / Empty or single node：head == NULL 時不能存取 head->next（會崩潰）。開頭就檢查並直接回傳。/ Guard against NULL before dereferencing head->next, otherwise it crashes.
• 一定要斷環 / Must break the circle：接成環後如果忘了把新尾巴的 next 設成 NULL，回傳的串列會是無限循環，LeetCode 會判定錯誤或超時。/ After circularizing, you must set the new tail's next to NULL, or the returned list loops forever.
• 步數 off-by-one / Step count off-by-one：新尾巴是第 n-k 個節點（1-indexed），從頭走 n-k-1 步才會停在它身上，而不是 n-k 步。走查那一節示範了這個容易搞錯的地方。/ The new tail is the (n-k)-th node; walk n-k-1 steps (not n-k) to land on it.