给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
没想到居然是一个困难题
循环使用 2个链表合并的思路处理
时间复杂度：由于除第一个链表外，其他每个链表都要被遍历多次，
等差数列：
第一次合并后，链表长度：2n
第二次合并后，链表长度：3n
第k-1次合并后，链表长度：kn
合计遍历(2+k)n*(k-1)/2=O(k^2*n)
空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(list1, list2):
dummy = ListNode()
p = dummy
while list1 and list2:
if list1.val < list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
p.next = list1 if list1 else list2
return dummy.next
if len(lists) == 0:
return None
p = lists[0]
for i in range(1, len(lists)):
p = mergeTwoLists(p, lists[i])
return p
|
分治+归并
k个数组，先两两合并，然后逐步归并。
划分深度为logk层，每层每个数都要遍历一次，每层k*n个数
时间复杂度O(logk * kn)
空间复杂度：栈空间logk，
若改为递归，则实际需要kn的额外空间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def mergeTwoLists(list1, list2):
if not list1: return list2
if not list2: return list1
dummy = ListNode()
p = dummy
while list1 and list2:
if list1.val < list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
p.next = list1 if list1 else list2
return dummy.next
def mergeHelper(lists, left, right):
if left == right: return lists[left]
if left < right:
mid = left + (right-left)//2
list1 = mergeHelper(lists, left, mid)
list2 = mergeHelper(lists, mid+1, right)
return mergeTwoLists(list1, list2)
else:
return None
return mergeHelper(lists, 0, len(lists)-1)
|
同时比较k个链表中开头的值，并用最小堆优化
时间复杂度：n个节点，k为最小堆的大小，每个节点必进出最小堆一次,堆调整O(logk),整体O(nlogk)
空间复杂度：即为堆的大小，O(logk)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
from heapq import heappush, heappop
heaq = []
for i in range(len(lists)):
if lists[i]:
heappush(heaq, (lists[i].val, i))
dummy = ListNode()
head = dummy
while heaq:
_, min_index = heappop(heaq)
head.next = lists[min_index]
head = head.next
lists[min_index] = lists[min_index].next
if lists[min_index]:
heappush(heaq, (lists[min_index].val, min_index))
return dummy.next
|
