给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表
示例 1：
输入：
l
i
s
t
s
=
[
[
1
,
4
,
5
]
,
[
1
,
3
,
4
]
,
[
2
,
6
]
]
lists = [[1,4,5],[1,3,4],[2,6]]
lists=[[1,4,5],[1,3,4],[2,6]]
输出：
[
1
,
1
,
2
,
3
,
4
,
4
,
5
,
6
]
[1,1,2,3,4,4,5,6]
[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1
−
>
4
−
>
5
,
1
−
>
3
−
>
4
,
2
−
>
6
]
[ 1->4->5, 1->3->4, 2->6 ]
[1−>4−>5,1−>3−>4,2−>6]
将它们合并到一个有序链表中得到。
1
−
>
1
−
>
2
−
>
3
−
>
4
−
>
4
−
>
5
−
>
6
1->1->2->3->4->4->5->6
1−>1−>2−>3−>4−>4−>5−>6
示例 2：
输入：
l
i
s
t
s
=
[
]
lists = []
lists=[]
输出：
[
]
[]
[]
示例 3：
输入：
l
i
s
t
s
=
[
[
]
]
lists = [[ ]]
lists=[[]]
输出：
[
]
[ ]
[]
提示：
对于这种数组排序的问题，有个直接的思路是把链表的节点值取出进行数组排序，再生成链表，性能非常好（数组排序做了很多优化），但为了体现算法逻辑，一般采取一些比较能体现算法思维的求解方法。
在之前有道题目与本题相似，就是《LeetCode_21_简单_合并两个有序链表》，当中有一个迭代的方法，设置一个哨兵节点，在每次迭代的时候把指针指向两个列表中较小的节点，直到某一链表指向空，此时再把另一链表的剩余部分接到结果链表的结尾。
而对于多个升序链表的合并，可以用以下的思路：
题解来源：灵茶山艾府
对于多个升序链表，同样的可以设立一个哨兵节点 dummy不断指向链表地最小值，这里的题解思路用的是最小堆，且对最小堆的大小函数进行重写，当然，也可以用其他的数据结构，但要能够实现结果链表指向下一个节点的同时，该节点所属的链表的头节点也向后更新。
如下对
L
i
s
t
N
o
d
e
ListNode
ListNode 的魔术方法 __lt__ 进行重写，该方法用在比大小时调用，重写该方法，即使得
L
i
s
t
N
o
d
e
ListNode
ListNode 对象能够直接根据
v
a
l
val
val 属性值比大小。该算法的时间复杂度为
O
(
n
l
o
g
k
)
O(nlogk)
O(nlogk)，空间复杂度为
O
(
k
)
O(k)
O(k)。
ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大小
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
cur = dummy = ListNode() # 哨兵节点，作为合并后链表头节点的前一个节点
h = [head for head in lists if head] # 初始把所有链表的头节点入堆
heapify(h) # 堆化
while h: # 循环直到堆为空
node = heappop(h) # 剩余节点中的最小节点
if node.next: # 下一个节点不为空
heappush(h, node.next) # 下一个节点有可能是最小节点，入堆
cur.next = node # 合并到新链表中
cur = cur.next # 准备合并下一个节点
return dummy.next # 哨兵节点的下一个节点就是新链表的头节点
执行用时：67 ms
消耗内存：18.88 MB