力扣top100-23. 合并K个升序链表-优先级队列、归并排序
题目：
- 合并K个升序链表
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
给你一个链表数组，每个链表都已经按升序排列。将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
算法选择1：
合并俩升序列表会，那么合并n个就可以使用归并呗
就像归并排序一样
但是，注意会议归并排序怎么做：
这是一个自顶向下的分治问题，
也就是递归划分子问题
所以需要三个函数：
一个解答方法，一个归并方法，一个合并两俩链表方法
代码：
public ListNode mergeKLists(ListNode[] lists) {
if(lists.length==0){
return null;
}
return merge(lists,0,lists.length-1);
}
//合并问题的划分，划分为合并子问题
public ListNode merge(ListNode[] lists,int first,int last){
if(first==last){
return lists[first];
}
int mid=(last+first)/2;
return merge2List(merge(lists,first,mid),merge(lists,mid+1,last));
}
//合并俩链表
public ListNode merge2List(ListNode list1,ListNode list2){
ListNode head=new ListNode(0,null);
ListNode tail=head;
while(list1!=null&&list2!=null){
if(list1.val算法选择2：
最开始的时候也考虑过，写个大循环
每次从所有链表中摘下来最小的元素插入结果链中，
但是k个元素取最小的，就需要每次都排一个序
但是这个选取最小元素的过程，可以不排序，而是使用优先队列
PriorityQueue
这个效率反而没有第一个高
代码：
public ListNode mergeKLists1(ListNode[] lists) {
if(lists.length==0){
return null;
}
PriorityQueue pq=new PriorityQueue<>(new Comparator(){
@Override
public int compare(ListNode l1, ListNode l2) {
return (int)(l1.val-l2.val);//啥意思！越小的优先级越高
}
});
for (int i = 0; i