📌 给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
合并 K 个排序链表
1
2
| 输入：lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
输出：[1, 1, 2, 3, 4, 4, 5, 6]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| def mergeKLists(lists):
"""顺序合并，效率不是很高"""
def merge(l1, l2):
d = c = ListNode(-1)
while l1 and l2:
if l1.val <= l2.val:
c.next, l1 = l1, l1.next
else:
c.next, l2 = l2, l2.next
c = c.next
c.next = l1 if l1 else l2
return d.next
ans = None
for i in lists:
ans = merge(ans, i)
return ans
mergeKLists([l1, l2])
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| def mergeKLists(lists):
"""使用堆"""
import heapq
dummy = ListNode(0)
p = dummy
head = []
for i in range(len(lists)):
if lists[i]:
heapq.heappush(head, (lists[i].val, i))
lists[i] = lists[i].next
while head:
val, idx = heapq.heappop(head)
p.next = ListNode(val)
p = p.next
if lists[idx]:
heapq.heappush(head, (lists[idx].val, idx))
lists[idx] = lists[idx].next
return dummy.next
|
