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