LeetCode23 合并K个排序链表（关于Java和c中的比较器）

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

样例

示例1

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例2

输入：lists = []
输出：[]

示例3

输入：lists = [[]]
输出：[]

算法

使用“堆”来处理，根据val排好序，只需要每次输出堆顶的元素

时间复杂度 O(nlogn)

参考文献

https://leetcode-cn.com/problems/merge-k-sorted-lists/solution/duo-tu-yan-shi-23-he-bing-kge-pai-xu-lian-biao-by-/

Java 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists == null || lists.length == 0)
            return null;

    PriorityQueue<ListNode> res = new PriorityQueue(new Comparator<ListNode>(){
        public int compare(ListNode o1,ListNode o2){
            return o1.val - o2.val;
        }      
    });

    ListNode dummy = new ListNode(-1);
    ListNode tail = dummy;

    for(int i = 0;i < lists.length;i ++)
    {
        while(lists[i] != null)
        {
            res.add(lists[i]);
            lists[i] = lists[i].next;
        }
    }

    while(!res.isEmpty())
    {
        dummy.next = res.poll();
        dummy = dummy.next;
    }
       dummy.next = null;
       return tail.next;
    }
}

补充

关于C++和Java的比较器写法

1、我的理解

我相信大家看视频的时候，看到y总写的这段代码一定很疑惑，尤其是不熟悉C++的同学，

    struct Cmp {
        bool operator() (ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };

在说明这个问题之前，要先注意的是，Java和C++中利用优先序列Priority_Queue构造“堆”时，Java默认构造的是小根堆，而后者默认的是大根堆，所以这一题我们要构造“堆”这个数据结构,需要考虑两个方面：
1）构造的是小根堆；
2）小根堆需要以节点值val来构造；

所以需要改写一下比较器，让它以val值来构建一个小根堆，那么这里return a->val > b->val，为什么y总说要将”<”变成”>”号就可以了呢？比较器中更精确的解释和理解，数据降序和升序的确定是根据返回值-1，0，1来确定的，无论在Java和C中源码都是根据这几个值来确定的，我们没有必要去理解的那么透彻，理解y总在回复中说的其实就足够了：

所有STL容器和库函数默认使用的是小于号，如果加上greater<>参数，那么会默认使用大于号。在上面的代码中优先队列会默认用一对小括号表示小于号，并且默认会构造一个大根堆，所以我们把小括号里的关系变一下，最后就可以得到小根堆了。

这句话的意思是在c中比较器构建大根堆的过程中，即这一段代码原本应该是renturn a < b;我们将其改写成return a > b后，优先队列构造“堆”这个数据结构时构造的就是小根堆了，return a->val >b ->val即让其按照节点的数值来构造小根堆。

2、和java的比较

Java中比较器和C++中比较器的代码和写法很类似，要根据return值，来判断降序和升序不太好理解，学习和工作估计都用不上，只需要记住以下结论就可以，Java比较器的通常写法：

PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
 @Override
 public int compare(Integer o1, Integer o2){
 return o1.compareTo(o2);
 }
});

1）这里return o1.compareTo(o2)表示构建小根堆，等价于 return o1 - o2；
2）同样的若是想要在Java中构建大根堆，只需要将return o1.compareTo(o2)改写为return o2.compareTo(o1)，等价于 return o2 - o1。
3）可以按照如下方式理解，如果觉得理解有困难，直接作为结论背下来也可以：

// 最小优先队列，直接 return o1.compareTo(o2);
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){
 @Override
 public int compare(Integer o1, Integer o2){
 return o1 < o2 ? -1 : 1;
 /* e.g., return o1.compare(o2); */
 }
});
// 最大优先队列，则反过来 return o2.compareTo(o1);

！！！！这里的o1和o2是有顺序的，o1代表后进元素而o2代表先进元素，由于源码中新入队元素x是在第1个参数的位置，因此最大/最小优先队列主要根据第1个参数的大小关系来判断。

//对于最大堆，当x>e时，让x上升，则 x>e时返回负数，即
int compare(Integer x, Integer e){
 return x > e ? -1 : 1;
}
//对于最小堆，当x<e时，让compare(x, e) < 0，即
int compare(Integer x, Integer e){
 return x < e ? -1 : 1; // return x.compareTo(e);
}