Merge k Sorted Lists

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

Naive Way:This question is asked on My Algorithm Course Mid-term Exam. Unfortunately, I didn't work thought it. But now, I know two methods to this question in O(nlogk) run time.

The first method is keep a heap. Push the head of each list into the heap. Pop the min from the heap and push its next into the heap. This method is an ideal way to solve the problem.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     Comparator<ListNode> c = new Comparator<ListNode>(){  
       @Override  
       public int compare(ListNode a, ListNode b){  
         if(a.val > b.val) return 1;  
         else if(a.val < b.val) return -1;  
         else return 0;  
       }  
     };  
     PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), c);  
     // initialize heap  
     for(int i = 0;i < lists.size();i++) if(lists.get(i)!=null) heap.offer(lists.get(i));  
     // pop from heap until empty  
     while(!heap.isEmpty()){  
       cur.next = heap.poll();  
       cur = cur.next;  
       if(cur.next!=null) heap.offer(cur.next);  
     }  
     return fake.next;  
   }  
 }  

Another way is great, too. Keep merge the lists two by two until there is only one list. And for merge two lists, I can use former way in Merge Two Sorted Lists.

 public class Solution {  
   public ListNode mergeKLists(List<ListNode> lists) {  
     // edge case  
     if(lists.size()==0) return null;  
     for(int i = 1;i < lists.size();i*=2)  
       for(int j = 0;j+i < lists.size();j+=2*i)  
         lists.set(j,mergeTwoSortedLists(lists.get(j), lists.get(j+i)));  
     return lists.get(0);  
   }  
   private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2){  
     if(l1==null) return l2;  
     else if (l2==null) return l1;  
     if(l1.val < l2.val){  
       l1.next = mergeTwoSortedLists(l1.next, l2);  
       return l1;  
     }else{  
       l2.next = mergeTwoSortedLists(l1, l2.next);  
       return l2;  
     }  
   }  
 }