Leetcode 23 Merge k Sorted Lists

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

Solution 1:  Use divide and conquer: if we solved left half and right half, just use merge two to combine the final result. Recursively do this. Complexity will be O(nlogk).

 public class Solution {  
   public ListNode mergeKLists(ListNode[] lists) {  
     int n=lists.length;  
     if (n<=0) return null;  
     return merge(lists,0,n-1);  
   }  
   private ListNode merge(ListNode[] lists, int lo, int hi) {  
     if (lo==hi) return lists[lo];  
     int mid=lo+(hi-lo)/2;  
     ListNode l1=merge(lists,lo,mid);  
     ListNode l2=merge(lists,mid+1,hi);  
     return mergeTwo(l1, l2);  
   }  
   private ListNode mergeTwo(ListNode l1, ListNode l2) {  
     ListNode dummy=new ListNode(0);  
     ListNode i=l1, j=l2, k=dummy;  
     while (i!=null || j!=null) {  
       if (i==null) {  
         k.next=j;  
         j=j.next;  
         k=k.next;  
       }  
       else if (j==null) {  
         k.next=i;  
         i=i.next;  
         k=k.next;  
       }  
       else if (i.val<j.val) {  
         k.next=i;  
         i=i.next;  
         k=k.next;  
       }  
       else {  
         k.next=j;  
         j=j.next;  
         k=k.next;  
       }  
     }  
     return dummy.next;  
   }  
 }  

Solution 2:  Bottom up way to do it.

 public class Solution {  
   public ListNode mergeKLists(ListNode[] lists) {  
     int n=lists.length;  
     if (n==0) return null;  
     for (int sz=1; sz<n; sz*=2) {  
       for (int i=0; i<n-sz; i+=sz*2) {  
         lists[i]=mergeTwo(lists[i],lists[i+sz]);  
       }  
     }  
     return lists[0];  
   }  
   private ListNode mergeTwo(ListNode l1, ListNode l2) {  
     ListNode dummy=new ListNode(0);  
     ListNode i=l1, j=l2, k=dummy;  
     while (i!=null || j!=null) {  
       if (i==null) {  
         k.next=j;  
         j=j.next;  
         k=k.next;  
       }  
       else if (j==null) {  
         k.next=i;  
         i=i.next;  
         k=k.next;  
       }  
       else if (i.val<j.val) {  
         k.next=i;  
         i=i.next;  
         k=k.next;  
       }  
       else {  
         k.next=j;  
         j=j.next;  
         k=k.next;  
       }  
     }  
     return dummy.next;  
   }  
 }