LeetCode 61. 旋轉鏈表：成環斷開法 C 語言 O(n) 時間 O(1) 空間解法

LeetCode 61. 旋轉鏈表：成環斷開法 C 語言 O(n) 時間 O(1) 空間解法

將鏈表向右旋轉 k 位。本文提供**成環→斷開**巧法：先連尾到頭成環，計算實際旋轉步數，找到新尾節點斷開，返回新頭。單次遍歷獲取長度與尾節點，邏輯極簡、無邊界分支。

題目大意

• 輸入：單鏈表 `head`，非負整數 `k`。
• 操作：向右旋轉 k 次（每次尾節點移到頭部）。
• 輸出：旋轉後的鏈表頭指針。
• 示例：1→2→3→4→5, k=2 → 4→5→1→2→3。

核心洞察：旋轉 = 斷開環

將鏈表尾接到頭形成環，旋轉 k 步相當於**新頭節點是原鏈表第 (n - k%n) 個節點**，新尾是其前驅。只需：

1. 遍歷得長度 `n` 並找到尾節點 `tail`。
2. `tail->next = head` 成環。
3. 計算 `k = n - k % n`（新頭距原頭步數）。
4. 從 `head` 走 `k-1` 步到新尾 `new_tail`。
5. `new_head = new_tail->next`；`new_tail->next = NULL` 斷開。
6. 返回 `new_head`。

C 語言實現

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    if (!head || !head->next || k == 0) return head; // 空/單節點/無需旋轉

    // 1. 遍歷計算長度 n，獲取尾節點 tail
    struct ListNode *tail = head;
    int n = 1;
    while (tail->next) {
        tail = tail->next;
        n++;
    }

    // 2. 成環
    tail->next = head;

    // 3. 計算實際旋轉步數（新頭距原頭步數）
    k = n - (k % n); // k 在 [1, n] 範圍內

    // 4. 找到新尾節點（走 k-1 步）
    struct ListNode *new_tail = head;
    for (int i = 1; i < k; i++) {
        new_tail = new_tail->next;
    }

    // 5. 斷開環，返回新頭
    struct ListNode *new_head = new_tail->next;
    new_tail->next = NULL;
    return new_head;
}

關鍵點解析

• k 取模：`k % n` 消除多餘整圈旋轉。`k = n - k%n` 將「右旋 k」轉為「左移 n-k」等價操作，統一為從頭走步數。
• 成環後必斷開：否則形成循環鏈表，後續遍歷死循環。
• 單次遍歷獲取 n 和 tail：無需額外遍歷，極致優化。
• 邊界處理：開頭判空、單節點、k=0 直接返回，避免除零、成環單節點自環等問題。

複雜度分析

• 時間：O(n) —— 單次遍歷計長 + 走 k-1 步（k < n）。
• 空間：O(1) —— 僅常數指針變量。

測試用例

常見錯誤避坑

1. **忘記 `k %= n`**：導致 `k` 可能巨大，走步數過多甚至死循環。
2. **成環後未斷開**：返回的鏈表成環，LeetCode 判題會檢測循環導致超時/錯誤。
3. **新尾查找步數錯誤**：走 `k` 步而非 `k-1` 步，導致新尾指向新頭，斷開後丟失數據。
4. **未處理 `k=0` 或 `k%n==0`**：若 `k=n`，`k = n - 0 = n`，走 `n-1` 步到尾節點，`new_head = tail->next = head`，正確但多繞一圈。開頭 `if(k==0) return head;` 更乾淨。

總結

旋轉鏈表通過**成環斷開**化繁為簡，單次遍歷、無分支邊界、邏輯閉環自洽。此技巧同樣適用於「鏈表左旋」、「找倒數第 k 個節點」等問題。掌握「尾接頭成環、取模消圈、斷開重組」三步曲，是鏈表操作進階必備技能。