/*
 * 演算法 / 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
}