No.23 合并 K 个升序链表

困难等级。

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

思路

我们想要一个从小到大的升序链表，即每次循环都取出一个最小的节点，然后依次连接，则得到一个升序的链表。
难点在于如何在 K 个链表中拿到一个最小的节点。
运用优先队列-小根堆的思想，堆顶得到的永远是最小值。我们可以先遍历所有链表，把每个链表的头结点入堆，即可得到第一个最小的节点（堆顶），然后取出最小节点的下一节点入堆排序，循环取出堆顶，依次连接即可得到一条升序链表。

技术栈：

优先队列 PriorityQueue<ListNode> pq = new PriorityQueue<>(length, (a, b) -> (a.val - b.val)); , 小根堆就设置 a.val - b.val
加入队列 pq.add(node)
堆顶出列 pq.poll()
判断堆是否为空 pq.isEmpty()

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        // 虚拟头节点
        ListNode dummy = new ListNode(-1), p = dummy;
        // 运用优先队列-小根堆的思想，根节点始终保持最小值
        PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, (a,b) -> (a.val - b.val));
        // 因为链表数组已经排序，先将链表数组内的头节点全部存入小根堆中
        for(ListNode head:lists) {
            // 如果链表非空，则入堆
            if(head != null) pq.add(head);
        }
        // 循环将链表的节点入堆，然后每次取出堆顶节点，则得到升序链表
        while(!pq.isEmpty()) {
            // 堆顶出列
            ListNode minNode = pq.poll();
            p.next = minNode;
            // 如果堆顶节点还有后续节点，则入堆排序
            if (minNode.next != null) {
                pq.add(minNode.next);
            }
            // p 往下走
            p = p.next;
        }
        return dummy.next;
    }
}