1 题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
2 解析
注意，最外层是列表，第二层是链表
如上面的[1,4,5]是链表1->4->5
（1）方法一
暴力求解，使用数组来存储所有元素，再对数组排序，最后用有序数组生成链表
（2）方法二
使用小顶堆，采用python包的heapq
（3）方法三
分而治之，使用两个链表的合并为有序的方法
3 python实现
（1）方法一
# 暴力求解，使用数组来存储所有元素，再对数组排序，最后用有序数组生成链表
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
temp = []
for i in lists:
while i:
temp.append(i.val)
i =i.next
temp.sort()
p = dummy = ListNode(0)
for j in temp:
p.next = ListNode(j)
p = p.next
return dummy.next
（2）方法二
# 使用小顶堆
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
import heapq
head = []
for i in lists:
while i:
heapq.heappush(head,i.val)
i = i.next
p = dummy = ListNode(0)
while head:
val = heapq.heappop(head)
p.next = ListNode(val)
p = p.next
return dummy.next
（3）方法三
# 分而治之，使用两个链表的合并为有序的方法
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if len(lists) ==0:
return ListNode().next
res = lists[0]
for i in range(1,len(lists)):
res = self.mergeTwoList(res,lists[i])
return res
def mergeTwoList(self, a:ListNode,b:ListNode) ->ListNode:
if not a:
return b
if not b:
return a
p,q = a,b
tail = head = ListNode(0)
while p and q:
if p.val <q.val:
tail.next = p
p = p.next
else :
tail.next = q
q = q.next
tail = tail.next
tail.next =q if q else p
return head.next
