25. Reverse Nodes in k-Group

Input:  head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

/*
 * 演算法 / Algorithm:
 * 用 dummy 虛擬頭簡化接線；每輪先數 k 個確認整組存在，
 * 再用三指標原地反轉這 k 個節點，然後縫回前後兩段。
 * Use a dummy head; each round verify k nodes exist, reverse them
 * in place with three pointers, then re-stitch the joints. O(n) time, O(1) space.
 */

// LeetCode 的節點定義（此處僅為說明，實際由平台提供）
// LeetCode's node definition (shown for reference; the platform provides it)
// struct ListNode { int val; struct ListNode *next; };

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    // 建立虛擬頭節點，next 先指向原本的 head
    // Create a dummy node whose next points to the original head.
    // 好處：反轉第一組時，dummy 扮演「上一組的尾巴」，不用寫特例
    // Benefit: dummy acts as the "previous group's tail" so the first group needs no special case
    struct ListNode dummy;        // 放在堆疊上，函式結束前都有效 / lives on the stack, valid until we return
    dummy.next = head;            // dummy 接到真正的頭 / dummy links to the real head

    // groupPrev：目前這一組「前面」的那個節點（一開始是 dummy）
    // groupPrev: the node just before the current group (starts as dummy)
    struct ListNode* groupPrev = &dummy;   // & 取位址，得到指向 dummy 的指標 / & takes the address of dummy

    while (1) {                   // 無窮迴圈，內部用 break 跳出 / infinite loop, we break out inside
        // ---- 第一步：往後數 k 個，確認這一組是完整的 ----
        // ---- Step 1: walk k nodes ahead to confirm a full group exists ----
        struct ListNode* kth = groupPrev;   // 從 groupPrev 開始數 / start counting from groupPrev
        for (int i = 0; i < k; i++) {       // 走 k 步 / take k steps
            kth = kth->next;                // -> 是「跟著指標找下一個節點」/ -> follows the pointer to the next node
            if (kth == NULL) {              // 走到底還沒數滿 k 個 / ran off the end before reaching k
                return dummy.next;          // 剩下的保持原樣，直接回傳結果 / leftover stays as-is; return the answer
            }
        }
        // 走到這裡，kth 就是這一組的第 k 個（最後一個）節點
        // Now kth is the k-th (last) node of this group.

        // ---- 第二步：記下反轉前後需要用到的邊界節點 ----
        // ---- Step 2: remember the boundary nodes we'll need ----
        struct ListNode* nextGroup = kth->next;   // 下一組的開頭 / the head of the next group
        struct ListNode* groupStart = groupPrev->next;  // 這組原本的頭（反轉後會變成尾）/ this group's old head (becomes the tail)

        // ---- 第三步：三指標原地反轉這 k 個節點 ----
        // ---- Step 3: reverse the k nodes in place with three pointers ----
        struct ListNode* prev = nextGroup;   // 反轉時的「前一個」，先設成下一組開頭，反轉完組尾就自動接上下一組
                                             // 'prev' starts as nextGroup so the tail auto-links to the next group
        struct ListNode* cur = groupStart;   // 從這組的第一個節點開始反轉 / current node, start at the group's head
        while (cur != nextGroup) {           // 反轉到碰到下一組為止（正好 k 個）/ stop when we reach the next group (exactly k nodes)
            struct ListNode* nxt = cur->next;// 先存下一個，否則改了指標就找不到它 / save next first, or we lose it after re-linking
            cur->next = prev;                // 把箭頭反過來指向前一個 / flip this node's arrow to point backward
            prev = cur;                      // prev 前進到目前節點 / advance prev to current
            cur = nxt;                       // cur 前進到剛剛存下的下一個 / advance cur to the saved next
        }
        // 迴圈結束後，prev 指向這組反轉後的新頭（原本的 kth）
        // After the loop, prev points to the reversed group's new head (the old kth).

        // ---- 第四步：把反轉後的組頭接回前一組 ----
        // ---- Step 4: connect the previous group to the new head ----
        groupPrev->next = prev;              // 上一組尾巴 -> 這組新頭 / previous tail -> this group's new head

        // ---- 第五步：把 groupPrev 移到這組的尾巴，準備下一輪 ----
        // ---- Step 5: move groupPrev to this group's tail for the next round ----
        groupPrev = groupStart;              // groupStart 反轉後正好是這組的尾巴 / groupStart is now the tail
    }
    // 迴圈只會透過上面的 return 離開 / the loop only exits via the return above
}

/*
 * 演算法 / Algorithm:
 * 與 C 版完全相同：dummy 虛擬頭 + 每輪數 k 個確認整組 + 三指標原地反轉 + 縫回接點。
 * Same as the C version: dummy head + verify k nodes each round + three-pointer
 * in-place reversal + re-stitch the joints. O(n) time, O(1) extra space.
 */

// LeetCode 提供的節點定義 / node definition provided by LeetCode:
// struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // dummy 虛擬頭：用花括號 {} 建立值為 0、next 為 nullptr 的節點
        // dummy head: brace-init makes a node with val 0 and next nullptr
        ListNode dummy;                 // 在堆疊上，函式回傳前都有效 / on the stack, valid until we return
        dummy.next = head;              // 接到真正的頭 / link to the real head

        // groupPrev：目前這組前面的節點 / the node just before the current group
        ListNode* groupPrev = &dummy;   // 取 dummy 的位址 / address-of dummy

        while (true) {                  // 內部用 return 跳出 / we exit via return inside
            // 往後數 k 個，確認整組存在 / walk k nodes to confirm a full group exists
            ListNode* kth = groupPrev;
            for (int i = 0; i < k; ++i) {
                kth = kth->next;        // 沿 next 前進 / advance along next
                if (kth == nullptr)     // 不足 k 個：剩餘保持原樣 / fewer than k left: keep as-is
                    return dummy.next;  // 回傳結果 / return the result
            }

            // 記下邊界 / record boundaries
            ListNode* nextGroup  = kth->next;         // 下一組開頭 / start of next group
            ListNode* groupStart = groupPrev->next;   // 這組原本的頭（將變成尾）/ old head (becomes tail)

            // 三指標原地反轉 k 個節點 / reverse k nodes in place with three pointers
            ListNode* prev = nextGroup;   // 讓組尾反轉後自動接上下一組 / tail auto-links to next group
            ListNode* cur  = groupStart;  // 從組頭開始 / start at the group head
            while (cur != nextGroup) {    // 反轉直到碰到下一組（正好 k 個）/ until we reach next group (exactly k)
                ListNode* nxt = cur->next;// 先保存下一個 / save next before overwriting
                cur->next = prev;         // 反轉箭頭 / flip the arrow backward
                prev = cur;               // prev 前進 / advance prev
                cur  = nxt;               // cur 前進 / advance cur
            }
            // 此時 prev 是反轉後的新組頭 / prev is now the reversed group's new head

            groupPrev->next = prev;       // 前一組尾 -> 新組頭 / previous tail -> new head
            groupPrev = groupStart;       // groupStart 現在是這組的尾，成為下輪的 groupPrev / it's the tail now
        }
    }
};