解題說明
Reverse Nodes in k-Group
題目描述：給定一個鏈結串列的頭節點 head 和整數 k，將鏈結串列每 k 個節點一組進行反轉，若最後剩餘的節點數不足 k 個，則保持原順序不變。不可更改節點的值，只能改變節點的指標。
解題思路：我們採用迭代搭配「虛擬頭節點（dummy node）」的方式，逐組反轉鏈結串列。
核心步驟：
- 建立一個虛擬頭節點
dummy，方便統一處理邊界。 - 使用指標
groupPrev指向每組反轉前的前驅節點。 - 每次先向前探測
k步，確認剩餘節點夠k個；若不夠，停止（保留原序）。 - 對這
k個節點進行迭代反轉：利用prev、curr指標逐一翻轉指向。 - 反轉完後，將
groupPrev的next接上反轉後的頭節點，原頭節點（現為尾節點）接上下一組的起始。 - 移動
groupPrev到當前組的尾節點，繼續下一輪。
這樣整個過程是 O(n) 時間、O(1) 空間（不計遞迴版本的堆疊）。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點恰好被訪問常數次：一次探測（getKth）、一次反轉，總共 O(n)。
空間複雜度：O(1) — 迭代版本只使用固定數量的指標變數，不需要額外空間；若使用遞迴版本則為 O(n/k) 的遞迴堆疊深度。
虛擬碼
1. Create a dummy node pointing to head; set groupPrev = dummy
2. Loop forever:
a. Call getKth(groupPrev, k) to find the k-th node from groupPrev
b. If no k-th node exists (fewer than k remaining), break
c. Set groupNext = kth->next (node after current group)
d. Reverse the k nodes between groupPrev and groupNext:
- Initialize prev = groupNext, curr = groupPrev->next
- While curr != groupNext: save tmp=curr->next, curr->next=prev, prev=curr, curr=tmp
e. Save tmp = groupPrev->next (original first node, now tail of reversed group)
f. Set groupPrev->next = kth (connect new head of reversed group)
g. Set groupPrev = tmp (advance to new tail for next iteration)
3. Return dummy.next其他解法
方法一：遞迴法（Recursive Approach） 先遞迴處理第 k+1 個節點之後的串列，取得其反轉結果作為「後半部分的頭節點」，再反轉當前 k 個節點並拼接。程式碼更直觀，但遞迴深度為 O(n/k)，當 k=1 時退化為 O(n) 堆疊，存在 stack overflow 風險。時間複雜度 O(n)，空間複雜度 O(n/k)。
方法二：收集後整批反轉（Collect and Reverse） 使用一個暫存陣列收集每組的 k 個節點，整批反轉陣列後再重新連接。實作簡單，但需要 O(k) 額外空間存放每組節點，且每組都需要額外的記憶體分配，不符合 O(1) 空間要求。時間複雜度 O(n)，空間複雜度 O(k)。
延伸思考
- 如果要求每隔一組才反轉（即第 1 組反轉、第 2 組不動、第 3 組反轉……），如何修改演算法？
- 本題要求不能修改節點值，只能改變指標；如果允許修改節點值，有沒有更簡單的解法？其空間複雜度如何？
- 如何擴展此題，使得每組從最後一組開始反轉（即尾部優先分組），不足 k 個的那組放在最前面且保持原序？