[LeetCode解題攻略] 25. Reverse Nodes in k-Group

題目描述

給定一個鏈表，將鏈表的節點每 k 個一組進行反轉，並返回修改後的鏈表。如果節點總數不是 k 的倍數，則保留最後剩餘節點的順序。要求在不改變節點值的情況下進行反轉（即直接操作鏈表結構）。

條件：

• 鏈表的長度範圍是 0 <= n <= 5000。
• 節點的值範圍是 0 <= Node.val <= 1000。
• 1 <= k <= n。

範例 1：

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]
Explanation: 每 2 個節點一組進行反轉，結果為 [2,1,4,3,5]。

範例 2：

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]
Explanation: 每 3 個節點一組進行反轉，結果為 [3,2,1,4,5]。

範例 3：

Input: head = [1,2,3,4,5], k = 1
Output: [1,2,3,4,5]
Explanation: k = 1 時，鏈表保持不變。

範例 4：

Input: head = [1], k = 1
Output: [1]

解題思路

1. 遍歷鏈表，找出每 k 節點的範圍。
2. 將這 k 個節點進行反轉，並將反轉後的部分重新鏈接到整體鏈表。
3. 處理剩餘不足 k 個的部分，保持原樣。

解法一：模擬分組反轉

思路

1. 使用一個指針遍歷整個鏈表，找到每 k 個節點作為一組。
2. 每次反轉這一組內的節點，並將其鏈接到已處理的部分。
3. 如果剩餘節點不足 k，則不進行反轉。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 計算鏈表長度
        def getLength(node):
            length = 0
            while node:
                length += 1
                node = node.next
            return length

        # 反轉一段鏈表
        def reverseList(start, end):
            prev = None
            current = start
            while current != end:
                temp = current.next
                current.next = prev
                prev = current
                current = temp
            return prev

        # 虛擬節點
        dummy = ListNode(0)
        dummy.next = head
        prev_group = dummy

        # 獲取鏈表長度
        length = getLength(head)

        # 遍歷鏈表，每 k 個為一組進行反轉
        while length >= k:
            group_start = prev_group.next
            group_end = group_start
            for _ in range(k - 1):
                group_end = group_end.next
            
            next_group = group_end.next

            # 反轉當前組
            group_end.next = None
            prev_group.next = reverseList(group_start, None)
            group_start.next = next_group

            # 更新指針
            prev_group = group_start
            length -= k

        return dummy.next

時間與空間複雜度

• 時間複雜度：
• • 每次反轉操作需要遍歷 k 個節點，總共有 n/k 次反轉，因此時間複雜度為 O(n)，其中 n 是鏈表的節點數。
• 空間複雜度：
• • 使用了常數額外空間，空間複雜度為 O(1)。

解法二：遞迴法

思路

1. 對於前 k 個節點進行反轉。
2. 剩下的部分使用遞迴處理，並將反轉後的部分接回已處理的部分。
3. 基本情況：如果剩餘節點不足 k，則返回原鏈表。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 檢查是否有足夠的節點可以反轉
        current = head
        count = 0
        while current and count < k:
            current = current.next
            count += 1
        
        if count < k:
            return head

        # 反轉前 k 個節點
        prev = None
        current = head
        for _ in range(k):
            temp = current.next
            current.next = prev
            prev = current
            current = temp
        
        # 遞迴處理剩餘部分
        head.next = self.reverseKGroup(current, k)

        return prev

時間與空間複雜度

• 時間複雜度：
• • 與解法一相同，每次遞迴處理 k 個節點，因此時間複雜度為 O(n)。
• 空間複雜度：
• • 使用遞迴函數調用棧，最深遞迴深度為 n/k，因此空間複雜度為 O(n/k)。

解法三：迭代法

此方法與解法一相似，進行少量優化以提高效率和代碼可讀性。

思路

迭代法的核心在於使用指針遍歷鏈表，逐步反轉每一組 k 個節點，並在反轉完成後重新將每組節點正確地鏈接起來。過程中，保持指針的更新和臨時保存反轉區間的節點信息。

步驟如下：

1. 使用一個虛擬節點（dummy node）方便操作頭節點的連接。
2. 設置指針追蹤每組需要反轉的起點和終點。
3. 反轉 k 個節點，並記錄反轉後的頭尾節點。
4. 更新指針以處理下一組節點，直到鏈表中剩餘節點不足 k。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        # 輔助函數：反轉單向鏈表
        def reverseList(head):
            prev = None
            current = head
            while current:
                temp = current.next
                current.next = prev
                prev = current
                current = temp
            return prev, head  # 返回新的頭節點和尾節點
            
        # 建立虛擬節點
        dummy = ListNode(0)
        dummy.next = head
        prev_group = dummy  # 追蹤每組反轉後的尾節點

        while True:
            # 找到需要反轉的一組節點
            group_start = prev_group.next
            group_end = prev_group
            for _ in range(k):
                group_end = group_end.next
                if not group_end:
                    return dummy.next  # 如果不足 k 個節點，直接返回結果

            # 保存下一組的起點
            next_group = group_end.next
            group_end.next = None  # 暫時斷開鏈表

            # 反轉當前組
            reversed_head, reversed_tail = reverseList(group_start)

            # 將反轉後的節點接回原鏈表
            prev_group.next = reversed_head
            reversed_tail.next = next_group

            # 更新指針，為下一組做準備
            prev_group = reversed_tail

時間與空間複雜度

• 時間複雜度：
• • 每次反轉一組 k 個節點需要 O(k)，鏈表總共有 n/k 組，因此時間複雜度為 O(n)。
• 空間複雜度：
• • 僅使用了指針進行操作，額外空間為常數，因此空間複雜度為 O(1)。

總結

1. 模擬分組反轉 是最直觀的解法，適合初學者。
2. 遞迴法 更具可讀性，但遞迴深度可能成為性能瓶頸。
3. 針對大規模鏈表，應選擇迭代法以降低空間複雜度。

選擇適合的解法取決於具體場景，對於需要高效處理的應用場景，迭代法更為優秀。