参考链接
参考链接
1.优先队列PriorityQueue是Queue接口的实现，可以放基本数据类型的包装类（如：Integer，Long等）或自定义的类。
1）对于基本数据类型的包装类，优先队列中元素默认排列顺序是升序排列。
1. PriorityQueuequeue = new PriorityQueue(10,new Comparator () { public int compare(Integer e1, Integer e2) {//从大到小排序 return e2 - e1; }); 2. static Comparator cmp = new Comparator () { public int compare(Integer e1, Integer e2) {//从大到小排序 return e2 - e1; } }; PriorityQueue queue = new PriorityQueue (10,cmp); 3. PriorityQueue queue = new PriorityQueue (10);//默认，从小到大升序
2）自定义类：
要使用 Comparator定义排序方式
示例1. PriorityQueuequeue = new PriorityQueue (lists.size(), new Comparator (){//定义一个新的内部类 @Override public int compare(ListNode l1, ListNode l2){//按从小到大排序 return l1.val - l2.val; } }); 示例2. static Comparator cNode=new Comparator () { public int compare(Node o1, Node o2) {//长度升序排列；当长相同时，按宽降序排列 if(o1.chang!=o2.chang) return o1.chang-o2.chang; else return o2.kuan-o1.kuan; } };
2.比较器升降序排序说明：
Comparator
3.队列常用方法：
add：插入队尾元素，不成功会抛出异常
offer：插入队尾元素，不能被立即执行的情况下会返回true 或 false
remove：删除队头元素，如果不成功会返回false。
remove(Object o)：删除其中一个元素o，如果o有多个则只删除一个。
poll：删除队头元素，并返回删除的元素
peek：查询队顶元素
indexOf(Object o)：查询对象o的索引
contain(Object o)：判断是否容纳了元素
4.题目：
合并 k 个升序的链表并将结果作为一个升序的链表返回其头节点。
要求：时间复杂度 O(nlogn)O(nlogn)
import java.util.*;
public class Solution {
public ListNode mergeKLists(ArrayList lists) {
if(lists.size() == 0 || lists == null){
return null;
}
PriorityQueue queue = new PriorityQueue(lists.size(), new Comparator(){
@Override
public int compare(ListNode l1, ListNode l2){//从小到大排序
return l1.val - l2.val;
}
});
ListNode newhead = new ListNode(0);
ListNode pre = newhead;
pre.next = null;
for(ListNode list: lists){//list元素是链表，不是节点
if(list != null)
queue.add(list);
}
while(!queue.isEmpty()){
pre.next = queue.poll();//删除并非返回队头节点
pre = pre.next;
if(pre.next != null){//说明刚链接的是个链表，不是一个单独节点。但是我们想要的只是这个节点
queue.add(pre.next);
}
}
return newhead.next;
}
}
