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

自己对java的优先队列简直是太不熟悉了，没准以后学的透彻了会再来看看自己能否实现

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        //队列遵循先进先出，但是有时候需要在队列中基于优先级处理对象，
        //此题是返回最小值
        //也就是说PriorityQueue和Queue最大的区别是，出队是看优先级的
        //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){
                //把所有链表都加入到优先队列中，
                //优先队列会自己处理，叭值最小的节点放到最前面
                pq.offer(node);
            }

        }
        //添加一个虚拟节点（哨兵），帮助简化边界情况的判断
        ListNode dummyHead = new ListNode(-1);
        //合并成功之后的尾结点位置
        ListNode tail = dummyHead;
        //遍历优先队列，去除最小值出来
        while(!pq.isEmpty()){
            //去除优先队列，即最小的节点
            ListNode minNode  = pq.poll();
            //把这个节点连接到合并链表的尾部
            tail.next  = minNode;
            tail = minNode;
            //PriorityQueue实现了Queue接口，不允许放入null
            if(minNode.next != null){
                pq.offer(minNode.next);
            }
        }

        //多路归并的过程
        return dummyHead.next;
    }
}