LeetCode Reverse Nodes in k-Group：鏈表每 k 個一組翻轉

題目回顧

單鏈表每 k 個節點一組翻轉，不足 k 保持原序。要求 O(1) 空間，不可修改節點值。
例：1→2→3→4→5, k=2 → 2→1→4→3→5

核心邏輯：分組翻轉 + 連接

對於每組 k 個節點：

1. 檢查剩餘節點是否 ≥ k
2. 翻轉這 k 個節點（標準鏈表翻轉）
3. 將翻轉後的組連接到前一組尾部
4. 更新指針進入下一組

Python 代碼

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k <= 1: return head
        dummy = ListNode(-1)
        dummy.next = head
        pre_group = dummy
        
        while True:
            # 檢查是否有 k 個節點
            kth = pre_group
            for _ in range(k):
                kth = kth.next
                if not kth: return dummy.next
            
            # 翻轉 [pre_group.next, kth]
            group_next = kth.next
            prev, curr = group_next, pre_group.next
            while curr != group_next:
                nxt = curr.next
                curr.next = prev
                prev = curr
                curr = nxt
            
            # 連接
            tmp = pre_group.next  # 翻轉前的頭，現為尾
            pre_group.next = kth  # 翻轉後的頭
            pre_group = tmp       # 移到下一組前驅
        
        return dummy.next

關鍵點

• dummy 虛擬頭簡化頭部翻轉邏輯
• pre_group 指向當前組前一個節點
• 翻轉時 prev 初始化為 group_next，自動連接下一組
• 翻轉後 pre_group.next 指向新頭（原 kth），pre_group 更新為原頭（現尾）

複雜度

• 時間：O(n)
• 空間：O(1)