LeetCode 25 Reverse Nodes in k-Group - K 個一組翻轉鏈表

題目翻譯

給定單鏈表，每 k 個節點為一組進行翻轉，返回修改後的鏈表頭。若剩餘節點不足 k 個則保持原序。要求 O(1) 空間，只能修改節點指針，不能修改節點值。例：1→2→3→4→5，k=2 → 2→1→4→3→5；k=3 → 3→2→1→4→5。

遞歸解法（簡潔易懂）

1. 先檢查剩餘節點是否 ≥ k，不足則直接返回頭節點。
2. 翻轉前 k 個節點，得到新頭節點 newHead。
3. 原頭節點（現為尾節點）的 next 遞歸連接後續處理結果。
4. 返回 newHead。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* node = head;
        for (int i = 0; i < k; ++i) {
            if (!node) return head; // 不足 k 個
            node = node->next;
        }
        // 翻轉 [head, node) 區間
        ListNode* newHead = reverse(head, node);
        // 遞歸處理剩餘部分
        head->next = reverseKGroup(node, k);
        return newHead;
    }

    // 翻轉 [start, end) 區間，返回新頭
    ListNode* reverse(ListNode* start, ListNode* end) {
        ListNode* prev = end; // 翻轉後尾節點指向 end
        while (start != end) {
            ListNode* nxt = start->next;
            start->next = prev;
            prev = start;
            start = nxt;
        }
        return prev;
    }
};

迭代解法（O(1) 空間，無遞歸棧）

用虛擬頭節點 dummy，維護 pre（上一組尾節點）、cur（當前組頭）。每輪檢查是否有 k 個節點，有則翻轉並重新鏈接。

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *pre = &dummy, *cur = head;

    while (true) {
        // 檢查剩餘長度
        ListNode* node = cur;
        for (int i = 0; i < k; ++i) {
            if (!node) return dummy.next;
            node = node->next;
        }
        // 翻轉 k 個節點
        ListNode* prev = node; // 翻轉後尾部連接 node
        for (int i = 0; i < k; ++i) {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }
        // 重新鏈接
        ListNode* tmp = pre->next; // 原組頭，現為組尾
        pre->next = prev;          // pre 連接新組頭
        pre = tmp;                 // pre 移至組尾
        cur = node;                // cur 移至下一組頭
    }
}

複雜度

• 時間：O(n) — 每個節點被訪問常數次。
• 空間：遞歸版 O(n/k) 棧空間；迭代版 O(1)。

總結

本題是鏈表翻轉的進階版，核心是「區間翻轉」+「分組處理」。遞歸版代碼極短、邏輯清晰，面試首選；迭代版滿足嚴格 O(1) 空間要求。關鍵細節：翻轉函數的區間定義 [start, end)、翻轉後尾節點連接 end、組與組之間的指針重新鏈接。