Leetcode/各大家 -- 23. Merge k Sorted Lists (heap or Divide&Conquer)

23. Merge k Sorted Lists(heap or Divide&Conquer)
hard
https://leetcode.com/problems/merge-k-sorted-lists/

 LinkedIn Google Uber Airbnb Facebook Twitter Amazon Microsoft

思路1： use priority queue to sort nodes (need comparator).
            First add the start of each lists to queue since they're the min of cur sorted list.
            Keep get top from heap and merge it to new list.
            Key is once get the min node from queue, insert the next node of cur list if not null
Complexity： Time O(nlogK) -- for each node insertion in heap O(logK)
                       space O(K) for priority queue, # of k nodes in heap

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new Comparator<ListNode>(){
            @Override
            public int compare (ListNode o1, ListNode o2){
                return o1.val - o2.val;
            }
        });
        for(int i = 0; i < lists.length; i++ ){
            if(lists[i]!=null)heap.add(lists[i]);
        }
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(!heap.isEmpty()){
            cur.next = heap.remove();
            cur = cur.next;
            if(cur.next != null){//since it's sorted, keep adding the rest of cur list
                heap.add(cur.next);
            }
        }
        return dummy.next;
    }
}