题意

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

难度

困难

标签

排序、链表、堆

示例

输入：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

分析

合并 K 个升序链表，很容易就让我们想到之前做过的 021.合并两个有序链表，这道题是升级版，合并 K 个。

021 题解的思路是通过比较两个链表的头节点，更小的那个就是新链表的头节点，再从剩余的里面找到下一个节点。

那我们能不能用相同的方法来完成 K 个升序链表的合并呢？

第一个链表与第二个链表合并，然后新的链表再与第三个链表合并……，以此类推，看上去能实现我们的目的。

但很遗憾，这样做的话，每一次合并后的新链表就会非常臃肿，并且在与第 K 个链表合并时，之前链表的节点会多次被访问。

第一个链表被访问k - 1次，第二个链表被访问k - 2次……

看来不太行啊，我们需要另寻他路。

堆。

堆。

堆。

好了，我来告诉大家答案啦，我们可以把 k 个链表的节点都扔到堆中，然后就可以快速得到最小的那个节点。堆顶的那个节点就是最小的。

每次把堆顶的那个节点取出来放到新的链表里，是不是瞬间一道难题就变成了一道简单题呢？

先不着急看题解，我们来讲讲最小堆。

上图中的堆就叫最小堆，Min Heap，一种特殊的完全二叉树，满足以下性质：对于树中的每个非叶子节点，节...