合并 K 个升序链表

方法一：最小堆

1. 思路

（1）合并后的第一个节点 first，一定是某个链表的头节点（因为链表已按升序排列）。

（2）合并后的第二个节点，可能是某个链表的头节点，也可能是 first 的下一个节点。

举例：有 3 个链表 1->2->5，3->4->6，4->5->6。找到第一个节点 1 之后，第二个节点不是另一个链表的头节点，而是节点 1 的下一个节点 2。

（3）按照上面的过程继续思考，每当我们找到一个节点值最小的节点 x，就把节点 x.next 加入'可能是最小节点'的集合中。

（4）因此需要一个数据结构，它需要支持：

——能从数据结构中找到并移除最小节点。

——能插入节点。

（5）可以用最小堆实现。初始把所有链表的头节点加入堆，然后不断弹出堆中最小的节点 x，如果 x.next 不为空就加入堆中，循环直到堆为空。把弹出的节点按顺序拼接起来，就得到了答案。

（6）实现时，可用哨兵节点简化代码。

2. 复杂度分析

（1）时间复杂度：O(Llogm)，其中 m 为 lists 的长度，L 为所有链表的长度之和。

（2）空间复杂度：O(m)，堆中至多有 m 个元素。

附代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                heap.add(head);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            curr.next = node;
            curr = curr.next;
            if (node.next != null) {
                heap.add(node.next);
            }
        }
        return dummy.next;
    }
}