[LeetCode解題攻略] 23. Merge k Sorted Lists

題目描述

給定 k 個遞增排序的鏈表，將它們合併成一個遞增排序的鏈表，並返回合併後的鏈表。

範例 1：

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

範例 2：

Input: lists = []
Output: []

範例 3：

Input: lists = [[]]
Output: []

解題思路

將 k 個排序鏈表合併成一個排序鏈表是經典的合併問題，可以考慮以下幾種解法：

1. 暴力解法：將所有節點收集到一個列表中，排序後再組裝成一個新的鏈表。
2. 兩兩合併：反覆將兩個鏈表合併，直到所有鏈表合併完成。
3. 分治法：類似歸併排序，將 k 個鏈表分成兩半，遞歸合併。
4. 優先隊列/最小堆：利用最小堆（優先隊列）高效地合併節點。

解法一：暴力解法

思路

1. 遍歷所有鏈表節點，將它們的值存入一個列表中。
2. 對列表進行排序。
3. 根據排序後的結果構建新的鏈表。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        nodes = []
        
        # 收集所有節點的值
        for l in lists:
            while l:
                nodes.append(l.val)
                l = l.next
        
        # 排序節點
        nodes.sort()
        
        # 根據排序結果重新構建鏈表
        dummy = ListNode()
        current = dummy
        for val in nodes:
            current.next = ListNode(val)
            current = current.next
        
        return dummy.next

時間與空間複雜度

• 時間複雜度：收集節點的值需要 O(N)（其中 N 是所有鏈表節點的總數），排序需要 O(N log N)，總時間複雜度為 O(N log N)。
• 空間複雜度：O(N)，使用了額外的列表來存儲節點值。

解法二：兩兩合併

思路

1. 使用合併兩個排序鏈表的方式，依次合併鏈表。
2. 反覆合併，直到所有鏈表合併成一個。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        
        while len(lists) > 1:
            merged_lists = []
            
            # Merge two lists at a time
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged_lists.append(self.mergeTwoLists(l1, l2))
            
            lists = merged_lists
        
        return lists[0]
        
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        current = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        current.next = l1 if l1 else l2
        return dummy.next

時間與空間複雜度

• 時間複雜度：
• • 每次合併需要 O(N)，總共需要合併 log k 次，總時間複雜度為 O(N log k)，其中 N 是總節點數，k 是鏈表數量。
• 空間複雜度：
• • 使用了遞迴合併兩個鏈表，但遞迴深度固定，額外空間為 O(1)。

解法三：分治法

思路

1. 使用分治法，將鏈表分為左右兩半。
2. 遞歸地合併兩部分。
3. 最後返回合併後的結果。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        
        mid = len(lists) // 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        current = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        current.next = l1 if l1 else l2
        return dummy.next

時間與空間複雜度

• 時間複雜度：
• • 與兩兩合併法相同，為 O(N log k)。
• 空間複雜度：
• • 使用了遞迴分治，遞迴深度為 O(log k)，空間複雜度為 O(log k)。

解法四：最小堆法（優先隊列）

思路

1. 使用優先隊列（最小堆）存儲每個鏈表的當前節點。
2. 每次取出最小的節點，並將其後繼節點加入堆中。
3. 重複上述步驟，直到所有節點被處理完。

程式碼

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:        
        class HeapNode:
            def __init__(self, node):
                self.node = node

            def __lt__(self, other):
                return self.node.val < other.node.val
                
        heap = []
        
        # 初始化堆
        for l in lists:
            if l:
                heapq.heappush(heap, HeapNode(l))
        
        dummy = ListNode()
        current = dummy
        
        while heap:
            # 取出最小節點
            smallest = heapq.heappop(heap).node
            current.next = smallest
            current = current.next
            
            # 如果還有後繼節點，加入堆中
            if smallest.next:
                heapq.heappush(heap, HeapNode(smallest.next))
        
        return dummy.next

時間與空間複雜度

• 時間複雜度：
• • 每次操作堆需要 O(log k)，處理所有節點需要 O(N log k)，總時間複雜度為 O(N log k)。
• 空間複雜度：
• • 優先隊列存儲了最多 k 個節點，空間複雜度為 O(k)。

總結

對於 k 值較小時，分治法和兩兩合併法都表現不錯；當 k 值較大時，優先隊列法因其高效性表現最佳。