腾讯算法常见考题：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

合并两个有序链表是比较容易的，相信任何人都可以做到。那么如何合并 K 序链表呢？其实原理是一样的。我们可以利用优先级队列来寻找最小的节点。完整代码如下：

class Solution {


    public ListNode mergeKLists(ListNode[] lists) {

        if(lists.length==0){
            return null;
        }
        //虚拟节点
        ListNode head = new ListNode(0);
        ListNode tail = head;
        //优先队列
        PriorityQueue<ListNode> queue = new PriorityQueue<>(lists.length,(a, b)->(a.val-b.val));

        //将K个链表头节点合并最小堆
        for (ListNode node: lists) {
            if (node != null) {
                queue.add(node);
            }
        }

        while (!queue.isEmpty()) {
            //获取最小节点，放到结果链表中
            ListNode node = queue.poll();
            tail.next = node;
            
            if (node.next != null) {
                queue.add(node.next);
            }
            //指针链表一直往前
            tail = tail.next;
        }
        return head.next;
    }
}