Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Heap

Time Complexity:
Update the heap costs O(nklogk)

Space Complexity:
O(kn)
The result listnode costs O(kn) and the heap is always O(k)

思路

Step1: Create a min heap with size k, loop through the input array of listnode and put all headnode into the heap
Step2: Create a new listnode two store the sorted list
Step3: Do the following steps k*n times (total number of the listnode)
(1) Pop out the min of the heap, add it to the result listnode
(2) If this listnode has next, insert it into the heap and update the heap

*这题中的input中，k个listnode还有其中个别的等于Null的情况，所以要判断一下再加入minheap

代码

public ListNode mergeKLists(ListNode[] lists) {
    if(lists == null || lists.length == 0) return null;
    ListNode dummy = new ListNode(0);
    ListNode head = dummy;
    PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>(){
        public int compare(ListNode l1, ListNode l2){
            return l1.val - l2.val;
        }
    });
    
    for(int i = 0; i < lists.length; i++){
        if(lists[i] != null) minHeap.offer(lists[i]);
    }
    
    while(!minHeap.isEmpty()){
        ListNode min = minHeap.poll();
        head.next = min;
        head = head.next;
        if(min.next != null){
            minHeap.offer(min.next);
            min = min.next;
        }
    }
    return dummy.next;
}