题解 | #合并k个已排序的链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类ArrayList
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here
        // 队列是遵循先进先出的模式的，但是有的时候需要在队列中基于优先级处理对象
        //PriorityQueue 和 Queue的区别在于，他的出队顺序与元素优先级有关
        //对于PriorityQueue 调用 remove() 或者 poll() 方法，返回总是优先级最高的元素
        //java 中 priorityQueue通过二叉小顶堆实现
        //PriorityQueue默认是一个小顶堆，可以通过传入的自定义 Comparator 函数来实现大顶堆
        Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);

        //遍历所有链表
        for (ListNode node : lists) {
            //PriorityQueue实现了Queue接口 不允许放入null元素
            if (node != null) {
                //将所有的链表都加入优先队列当中
                //优先队列会根据自定义的Comparator函数处理
                //add(E e):
                //add()方法尝试将指定的元素插入此队列（如果立即可行且不会违反容量限制），成功时返回true，如果当前没有可用的空间，则抛出IllegalStateException。
                //这个方法通常用于那些有固定大小的队列，当你尝试添加一个元素到已满的队列时，它会抛出异常。
                //offer(E e):
                //offer()方法也尝试将指定的元素插入此队列，但如果立即执行此操作会失败或由于任何其他原因（例如，如果队列已关闭），则返回false。
                //与add()方法不同，如果队列已满，offer()不会抛出异常，而是返回false，表示添加操作没有成功。
                //offer()方法通常用于那些可能有容量限制的队列，但你不希望添加操作失败时抛出异常的情况。
                pq.offer(node);
            }
        }

        //添加一个虚拟的头节点
        ListNode dummy = new ListNode(-1);

        //合并成功之后的尾节点位置
        ListNode pre = dummy;

        //遍历优先队列，取出最小值出来
        while (!pq.isEmpty()) {

            //取出优先队列，即二叉堆的头结点，最小的节点
            ListNode minNode = pq.poll();

            //将这个节点连接到合并链表的尾部
            pre.next = minNode;

            //pre位置后移
            pre = minNode;

            //再把新的节点放入优先队列中进行比较
            if (minNode.next != null) {
                pq.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}