LeetCode 61 詳解：Rotate List (鏈表右旋 k 位)

題目描述

給定單鏈表頭節點 head 和非負整數 k，將鏈表向右旋轉 k 位。即最後 k 個節點移至頭部。

範例：1→2→3→4→5→NULL, k=2 → 4→5→1→2→3→NULL

解題思路

1. 計算鏈表長度 len，同時找到尾節點 tail
2. k %= len 處理 k ≥ len 情況（循環旋轉等價）
3. 若 k == 0 直接返回原頭
4. 找到新尾節點：第 len - k 個節點（0-indexed 為 len - k - 1）
5. 新頭 = newTail->next，斷開連接，tail->next = head

完整代碼

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next || k == 0) return head;
        
        // 1. 計算長度，找到尾節點
        int len = 1;
        ListNode* tail = head;
        while (tail->next) {
            ++len;
            tail = tail->next;
        }
        
        // 2. 處理 k >= len
        k %= len;
        if (k == 0) return head;
        
        // 3. 找到新尾節點 (第 len-k 個)
        ListNode* newTail = head;
        for (int i = 1; i < len - k; ++i) {
            newTail = newTail->next;
        }
        
        // 4. 重新連接
        ListNode* newHead = newTail->next;
        newTail->next = nullptr;
        tail->next = head;
        
        return newHead;
    }
};

執行過程圖解

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

len=5, tail=5
k=2%5=2
newTail 移動 len-k-1 = 2 步：1→2→3 (指向 3)
newHead = 4
斷開 3→4，連接 5→1
結果：4→5→1→2→3

複雜度分析

• 時間：O(n) — 兩次遍歷（計算長度 + 找新尾）
• 空間：O(1) — 僅常數指針

關鍵點總結

1. k %= len 必不可少，避免多餘旋轉
2. 單鏈表無法倒序遍歷，必須先算長度再正向找新尾
3. 邊界情況：空表、單節點、k=0、k=len 皆返回原頭
4. 形成環再斷開的替代寫法：tail->next = head 先成環，再移動 len-k 步斷開

總結

LeetCode 61 是鏈表基本操作題。核心步驟：測長、取模、找新尾、重連。注意 k %= len 處理大 k，以及空表/單節點邊界。代碼簡潔，考察指針操作熟練度。