1、前言

2、思路

这道题还是原来合并两个链表的思路，首先声明一个 dummy 节点，将 dummy 赋予 p，然后在 p 的角度不断的连接。只是原来只有两个链表，链接直接比较就行。现在有 k 个链表，所以不能直接比较，需要一个最小堆，堆的容量为链表头节点数组的长度。开始先将数组中的头节点加入到最小堆，如果堆不空则取出堆顶元素，用 p 来连接，然后 p 移动到链接的节点。然后怎么补充最小堆的元素呢？

需要先判断此时链接的节点后一个节点是否为空，不为空则可以加入。最后返回 dummy 的 next 节点即可。

3、代码

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0){
            return null;
        }
        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>(lists.length, new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val - o2.val;
            }
        });

        for (ListNode list : lists) {
            if(list != null) priorityQueue.add(list);
        }

        ListNode dummy = new ListNode();
        ListNode p = dummy;

        while(!priorityQueue.isEmpty()){
            ListNode minNode = priorityQueue.poll();
            p.next = minNode;
            p = p.next;
            if(minNode.next != null){
                priorityQueue.add(minNode.next);
            }
        }


        return dummy.next;
    }
}