25. Reverse Nodes in k-Group

Hard

Description

給定一個鏈結串列的頭節點 head，每 k 個節點一組進行反轉。如果剩餘節點不足 k 個，則保持原順序。只能修改節點本身，不能修改節點的值。

Example:

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

Intuition#

核心思路：每次檢查是否有足夠 k 個節點，若有則反轉這一段，再遞迴或迭代處理下一段。

本題是 206. Reverse Linked List 的進階版
關鍵操作：(1) 檢查剩餘節點是否 >= k (2) 反轉 k 個節點 (3) 連接反轉後的段落
需要仔細管理各段之間的指針連接

Approaches#

1: Recursive#

概念: 檢查是否有 k 個節點，若有則反轉前 k 個，將反轉後的尾部連接到遞迴處理剩餘部分的結果
時間複雜度: O(n) - 每個節點訪問常數次
空間複雜度: O(n/k) - 遞迴深度

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        // 檢查是否有 k 個節點
        var count = 0
        var curr = head
        while (curr != null && count < k) {
            curr = curr.next
            count++
        }
        if (count < k) return head

        // 反轉前 k 個節點
        var prev: ListNode? = null
        var node = head
        for (i in 0 until k) {
            val next = node!!.next
            node.next = prev
            prev = node
            node = next
        }

        // head 現在是反轉段的尾部，連接到遞迴結果
        head!!.next = reverseKGroup(node, k)

        return prev
    }
}

⭐2: Iterative with Dummy Head#

概念: 使用 dummy head，每次找到一組 k 個節點後反轉，用 groupPrev 和 groupNext 管理段落之間的連接
時間複雜度: O(n) - 每個節點訪問常數次
空間複雜度: O(1) - 只用常數指針

class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        val dummy = ListNode(0)
        dummy.next = head
        var groupPrev: ListNode = dummy

        while (true) {
            // 檢查是否有 k 個節點
            var kth = groupPrev
            for (i in 0 until k) {
                kth = kth.next ?: return dummy.next
            }
            val groupNext = kth.next

            // 反轉這一組
            var prev = groupNext
            var curr = groupPrev.next
            for (i in 0 until k) {
                val next = curr!!.next
                curr.next = prev
                prev = curr
                curr = next
            }

            // 更新連接
            val tmp = groupPrev.next!!
            groupPrev.next = prev
            groupPrev = tmp
        }
    }
}

反轉時 prev 初始化為 groupNext（下一組的第一個節點），而非 null。這樣反轉完成後，當前組的尾部自然連接到下一組的頭部。

補充：圖解迭代過程

以 [1,2,3,4,5], k=2 為例：

初始：  dummy -> 1 -> 2 -> 3 -> 4 -> 5
               groupPrev=dummy, kth=2, groupNext=3

第一輪反轉：prev 從 groupNext(3) 開始
  1.next = 3(prev), prev = 1
  2.next = 1(prev), prev = 2

連接：  dummy -> 2 -> 1 -> 3 -> 4 -> 5
               groupPrev=1

第二輪反轉：prev 從 groupNext(5) 開始
  3.next = 5(prev), prev = 3
  4.next = 3(prev), prev = 4

連接：  dummy -> 2 -> 1 -> 4 -> 3 -> 5
               groupPrev=3

第三輪：只剩 1 個節點 < k，回傳結果

🔑 Takeaways#

Pattern: 分段處理鏈結串列的模板：用 groupPrev/groupNext 界定每一段，段內操作完後更新連接
關鍵技巧: 反轉時把 prev 初始化為 groupNext 而非 null，巧妙省去後續的連接操作