给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = [[]]
输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按 升序 排列lists[i].length 的总和不超过 10^4
思路：参考合并两个有序链表方法：
# @lc code=start
# 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[ListNode]) -> ListNode:
prehead = ListNode(-1)
n=len(lists)
x=[[10**4+1]*n]
prev = prehead
while lists!= [[None]*n]:
list1=[]
for i in range(n):
if lists[i]:
list1.append(lists[i].val)
else:
list1.append(10**4+1)
if list1==x[0]:
break
index=list1.index(min(list1))
prev.next = lists[index]
lists[index]= lists[index].next
prev = prev.next
return prehead.next
对于该例子超时了
看下leetcode给出的一些方法：
两两合并：
最简单方法：采用分治法，利用之前的两两合并的链表，逐个将K个链表合并。但这样效率较低，时间上只比16%的提交优秀。
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists: return None
res = None #设置初始结果为空
for listi in lists: #逐个遍历 两两合并
res = self.mergeTwoLists(res, listi)
return res
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) #构造虚节点
move = dummy #设置移动节点等于虚节点
while l1 and l2: #都不空时
if l1.val < l2.val:
move.next = l1 #移动节点指向数小的链表
l1 = l1.next
else:
move.next = l2
l2 = l2.next
move = move.next
move.next = l1 if l1 else l2 #连接后续非空链表
return dummy.next #虚节点仍在开头
最后的两链表合并部分不变，上部的两两合并改成归并形式的递归操作
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
if not lists: return None
n = len(lists) #记录子链表数量
return self.mergeSort(lists, 0, n - 1) #调用归并排序函数
def mergeSort(self, lists: List[ListNode], l: int, r: int) -> ListNode:
if l == r:
return lists[l]
m = (l + r) // 2
L = self.mergeSort(lists, l, m) #循环的递归部分
R = self.mergeSort(lists, m + 1, r)
return self.mergeTwoLists(L, R) #调用两链表合并函数
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0) #构造虚节点
move = dummy #设置移动节点等于虚节点
while l1 and l2: #都不空时
if l1.val < l2.val:
move.next = l1 #移动节点指向数小的链表
l1 = l1.next
else:
move.next = l2
l2 = l2.next
move = move.next
move.next = l1 if l1 else l2 #连接后续非空链表
return dummy.next #虚节点仍在开头
最小堆：
思路：对所有的list中元素入堆，然后依次出堆到新的listnode中。
利用堆的数据结构，可以极大地简化代码。
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
import heapq #调用堆
minHeap = []
for listi in lists:
while listi:
heapq.heappush(minHeap, listi.val) #把listi中的数据逐个加到堆中
listi = listi.next
dummy = ListNode(0) #构造虚节点
p = dummy
while minHeap:
p.next = ListNode(heapq.heappop(minHeap)) #依次弹出最小堆的数据
p = p.next
return dummy.next
