题解 | #牛群的合并# Java

借助小根堆数据结构，每次选择最小的节点，如果最小的节点有下一个，就加进堆里面

• 掌握一下PriorityQueue借助Comparator初始化的方法

public class Solution {

    public ListNode mergeKLists (ListNode[] lists) {
        if (lists.length == 0) return null;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            public int compare(ListNode p1, ListNode p2) {
                return p1.val - p2.val;
            }
        });
        for (ListNode ln : lists) {
            if (ln != null ) pq.add(ln);
        }

        ListNode dummy = new ListNode(-1), cur = dummy;
        while (!pq.isEmpty()) {
            ListNode tmp = pq.poll();
            if (tmp.next != null) {
                pq.add(tmp.next);
            }
            cur.next = tmp;
            cur = cur.next;
        }

        return dummy.next;
    }
}