以 K 個節點為一組反轉單鏈表：演算法與 C 語言實現

以 K 個節點為一組反轉單鏈表：演算法與 C 語言實現

單鏈表的區塊反轉是經典的資料結構面試題目，也是實務開發中常見的操作。給定一個單鏈表與整數 k，目標是將鏈表每 k 個節點為一組進行反轉；若剩餘節點不足 k 個，則保持原序。

範例說明

輸入：1→2→3→4→5→6→7→8→NULL，k = 3
輸出：3→2→1→6→5→4→7→8→NULL

上例中，前兩組各 3 個節點（1-2-3、4-5-6）被反轉，最後剩餘 2 個節點（7-8）不足 k，故維持原順序。

核心思路

1. 使用三個指標 prev、curr、next 在區塊內進行原地反轉。
2. 記錄已處理節點數 count，當 count == k-1 時完成一組反轉。
3. 遞迴處理下一組：將當前組的原頭節點（反轉後的尾節點）的 next 指向遞迴返回的新頭節點。
4. 邊界條件：k <= 1 直接返回原鏈表；節點不足 k 時回滾已反轉的部分。

C 語言參考實作

Node* invertList(Node *head, int k) {
    if (k == 0 || k == 1) return head;

    Node *prev = head;
    Node *curr = prev->next;
    Node *next = curr ? curr->next : NULL;
    int count = 0;

    while (count < k - 1) {
        if (curr != NULL) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            count++;
        } else {
            // 節點不足 k 個，回滾已反轉部分
            curr = prev->next;
            prev->next = NULL;
            while (count > 0) {
                next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
                count--;
            }
            return prev;
        }
    }

    // 遞迴處理剩餘鏈表
    if (next != NULL)
        head->next = invertList(next, k);
    else
        head->next = NULL;

    return prev; // prev 為反轉後的新頭節點
}

複雜度分析

• 時間複雜度：O(n)，每個節點最多被訪問兩次（反轉與回滾）。
• 空間複雜度：O(n/k) 遞迴呼叫堆疊深度，若改用迭代可降為 O(1)。

常見陷阱與優化建議

• 遞迴版本在極長鏈表下可能導致堆疊溢位，生產環境建議改寫為迭代版本。
• 注意 k=0 或 k=1 的邊界情況，直接返回原鏈表避免無限遞迴。
• 使用 虛擬頭節點 可簡化頭節點變更的邏輯，使程式碼更易維護。