二 代码1 和合并2个升序链表类似，先对比链表头的k个数，这里用优先级队列(二叉树堆)来保存。 2 每次拿出二叉树堆中的最小值(即k个数中的最小值)，然后把当前链表的下一个节点入堆，始终保证是k个链表头，依次取最小值，直到排序完成
class Solution {
// 第一种写法：lambda表达式
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
PriorityQueue tempQueue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val); //用于存放k个待排序的链表头
ListNode dummy = new ListNode(-1); // 虚拟头节点
ListNode p = dummy;
for (ListNode head : lists){
if (head != null){
tempQueue.add(head); // 拿到k个链表头
}
}
while (!tempQueue.isEmpty()){
p.next = tempQueue.poll();
if (p.next.next != null){
tempQueue.add(p.next.next);
}
p = p.next;
}
return dummy.next;
}
-----------------------------------------------------------------------------------------
// 第二种写法： 匿名类
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0) return null;
//用于存放k个待排序的链表头
PriorityQueue tempQueue = new PriorityQueue<>(new Comparator() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});
ListNode dummy = new ListNode(-1); // 虚拟头节点
ListNode p = dummy;
for (ListNode head : lists){
if (head != null){
tempQueue.add(head); // 拿到k个链表头
}
}
while (!tempQueue.isEmpty()){
ListNode node = tempQueue.poll();
p.next = node;
if (p.next.next != null){
tempQueue.add(p.next.next);
}
p = p.next;
}
return dummy.next;
}
}
三 说明
1 通过看源码可以发现，优先级队列类一共提供了多种构造器，无参构造是默认队列长度为全局常量DEFAULT_INITIAL_CAPACITY，值为11。
比较器默认为null。其他有参构造器均可用户指定，形参为优先级队列initialCapacity和比较器comparator。
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
public PriorityQueue(Comparator comparator) {
this(DEFAULT_INITIAL_CAPACITY, comparator);
}
public PriorityQueue(int initialCapacity,
Comparator comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
2 因此本题在初始化优先级队列的时候可以指定容量，也可以自动扩容。
但是比较器默认是按照自然顺序natural ordering 来排序，这肯定不是这道题的需求，这道题需要按照链表节点的值的大小来排序，这时候需要我们自定义比较器Comparator。
Comparator是一个接口，其中定义了抽象的compare方法。本题通过重写该方法达到比较链表节点值的目的，因此便有了解法二的定义匿名类重写compare方法的写法：
PriorityQueuetempQueue = new PriorityQueue<>(new Comparator () { @Override public int compare(ListNode o1, ListNode o2) { return o1.val - o2.val; } });
还有解法一lambda表达式的写法，两者的效果都一样。
PriorityQueuetempQueue = new PriorityQueue<>((o1, o2) -> o1.val - o2.val);
根据比较器的规则，优先级队列将变为小顶堆或者大顶堆。
小顶堆，形参(o1, o2) return 前减后(o1-o2)；
大顶堆， 形参(o1, o2) return 后减前(o2-o1)；
