23. Merge k Sorted Lists

Hard

Key idea: using PriorityQueue to implement minimal heap

核心：用有限队列实现最小堆

Using PriorityQueue to do heap

English

1. add the head of each list to heap

2. poll out top of heap adding to new linked list

3. add this element's next to heap

4. until heap is empty

Chinese

PriorityQueue doesn't accept null, so before adding element, judge whether it is null

优先序列这种数据结构不接收空元素，所以在加入元素前先判断是否为空

PriorityQueue only accepts comparable elements, self-define data structure mustn't be comparable, so override comparator function of PriorityQueue is necessary

优先序列只接受能比较大小的元素，自定义的数据结构是不可比较的，因此必须重写comparator，然后用comparator去初始化优先序列

Override comparator and PriorityQueue instance

Comparator<ListNode> comparator = new Comparator<ListNode>(){
    @Override
    public int compare(ListNode node1, ListNode node2){
        if(node1.val>node2.val) return 1;
        else if(node1.val < node2.val) return -1;
        else return 0;
    }
};
          
Queue<ListNode> queue = new PriorityQueue<ListNode>(comparator);

English

Why using PriorityQueue to implement heap?

Because any element added to PriorityQueue, it will be sorted in $O(lg N)$ automatically in acceding order. Therefore, adding and deleting an element for PriorityQueue is $O(lg N)$ , find the smallest element is $O(1)$ . So solving this problem takes $O(nlgK)$

Chinese