題目描述
給定 k 個遞增排序的鏈表，將它們合併成一個遞增排序的鏈表，並返回合併後的鏈表。
範例 1：
Input: lists = [[1,4,5],[1,3,4],[2,6]]範例 2：
Output: [1,1,2,3,4,4,5,6]
Input: lists = []
Output: []
範例 3：
Input: lists = [[]]
Output: []
解題思路
將 k 個排序鏈表合併成一個排序鏈表是經典的合併問題，可以考慮以下幾種解法：
- 暴力解法：將所有節點收集到一個列表中，排序後再組裝成一個新的鏈表。
- 兩兩合併：反覆將兩個鏈表合併，直到所有鏈表合併完成。
- 分治法：類似歸併排序，將
k個鏈表分成兩半，遞歸合併。 - 優先隊列/最小堆：利用最小堆（優先隊列）高效地合併節點。
解法一：暴力解法
思路
- 遍歷所有鏈表節點，將它們的值存入一個列表中。
- 對列表進行排序。
- 根據排序後的結果構建新的鏈表。
程式碼
# 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)，使用了額外的列表來存儲節點值。
解法二：兩兩合併
思路
- 使用合併兩個排序鏈表的方式，依次合併鏈表。
- 反覆合併，直到所有鏈表合併成一個。
程式碼
# 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)。
解法三：分治法
思路
- 使用分治法，將鏈表分為左右兩半。
- 遞歸地合併兩部分。
- 最後返回合併後的結果。
程式碼
# 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)。
解法四：最小堆法（優先隊列）
思路
- 使用優先隊列（最小堆）存儲每個鏈表的當前節點。
- 每次取出最小的節點，並將其後繼節點加入堆中。
- 重複上述步驟，直到所有節點被處理完。
程式碼
# 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 值較大時，優先隊列法因其高效性表現最佳。
