LeetCode 61 Rotate List：鏈表旋轉的環形鏈表技巧

問題描述

給定單鏈表頭節點和整數 k，將鏈表向右旋轉 k 位。例如 1→2→3→4→5, k=2 → 4→5→1→2→3。

核心思路：成環 + 斷開

1. 遍歷鏈表得長度 len，並將尾節點連向頭節點形成環
2. 實際旋轉步數 = k % len（k 可能大於長度）
3. 新尾節點位於原頭節點前 `len - k%len` 步
4. 斷開環，返回新頭節點

完整代碼

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return nullptr;
        
        // 1. 成環並計算長度
        ListNode* tail = head;
        int len = 1;
        while (tail->next) {
            tail = tail->next;
            ++len;
        }
        tail->next = head;  // 形成環
        
        // 2. 找新尾節點
        int steps = len - k % len;
        ListNode* newTail = tail;
        for (int i = 0; i < steps; ++i)
            newTail = newTail->next;
        
        // 3. 斷開環
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        return newHead;
    }
};

關鍵細節

• 空鏈表/單節點：直接返回
• k 取模：避免多餘旋轉，`k % len` 為實際偏移
• 步數計算：`len - k%len` 步到達新尾節點（從原尾節點起算）
• 原地操作：O(1) 空間，O(n) 時間

圖解

原始：1 → 2 → 3 → 4 → 5 (len=5, k=2)
成環：1 → 2 → 3 → 4 → 5 ↘
         ↑_______________|
steps = 5 - 2%5 = 3
從 tail(5) 走 3 步：5→1→2→3 (newTail=3)
斷開：newHead=4, 3->next=null
結果：4 → 5 → 1 → 2 → 3

複雜度

• 時間：O(n)，兩次遍歷（成環+找新尾）
• 空間：O(1)