23. Merge k Sorted Lists Leetcode Java

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Solution:
1.Divide and Conquer
This solution is very similar to the merge sort. Basically it divided the list to two halfs and then merge the first half list to a linked list and merge the second half list to another linked list, then merge the two linked list together. So we have a merge two linked list sub-method called merge(),and we have a recursively divide and merge sub-method called helper(). 
Set the maximum length among all the K linked lists is n. So the merge() will take O(n*K).
The recursion equation is T(K)= 2T(K/2)+O(n*K), so the time complexity is O(nK*logK) according to the master theorem. The space complexity is O(logK) which is the size of the recursion stack.

 public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists==null || lists.size()==0) return null;  
     return helper(lists,0,lists.size()-1);  
   }  
   public ListNode helper(List<ListNode> lists, int l, int r){  
     if(l==r) return lists.get(l);  
     int m=(r-l)/2+l;  
     return merge(helper(lists,l,m),helper(lists,m+1,r));  
   }  
   public ListNode merge(ListNode headA, ListNode headB){  
     ListNode predummy=new ListNode(0);  
     predummy.next=headA;  
     ListNode pre=predummy;  
     while(headA!=null && headB!=null){  
       if(headB.val<headA.val){  
         ListNode temp=headB.next;  
         pre.next=headB;  
         headB.next=headA;  
         headB=temp;  
       }  
       else headA=headA.next;  
      pre=pre.next;  
     }  
     if(headB!=null) pre.next=headB;  
     return predummy.next;      
   }  

2. PriorityQueue Heap
We maintain a priorityqueue to store the listNode based on the value. The head of this queue is always the smallest one in this queue. Because the link lists are sorted, so we only need to add the subsequent node to the heap when its preceding node is retrieved. The size of the priorityqueue is K. To heapify up: insert/offer a new element will take O(logK) while to heapify down: remove/poll the minimum element will also take O(logK). 
So the total time complexity is (nK*O(logK)) for total O(n*K) listNodes. The space is the the size of the priorityqueue: O(K).

 public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists==null || lists.size()==0) return null;  
     PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(10,new Comparator<ListNode>(){  
       @Override  
       public int compare(ListNode l1, ListNode l2){  
         return l1.val-l2.val;  
       }   
     });  
     for(ListNode ls : lists){  
       if(ls!=null) pq.offer(ls);  
     }  
     ListNode predummy=new ListNode(0);  
     ListNode pre=predummy;  
     while(!pq.isEmpty()){  
       ListNode temp=pq.poll();  
       pre.next=temp;  
       pre=pre.next;  
       if(temp.next!=null) pq.offer(temp.next);   
     }  
     pre.next=null;  
     return predummy.next;  
   }