腾讯常考十道算法真题：合并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;
    }
}