Merge K Sorted Lists

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

This question looks very much similar to the merge step of external sorting.

http://en.wikipedia.org/wiki/External_sorting 

The time complexity of this merge takes O(nk) in our process because each time we take O(k) to find the minimum of each pass, and we have n passes. However, if we use a data structure of heap or tournament tree when finding the min element, the complexity can be reduced to O(nlogk).

public class ListNode {
   int val;
   ListNode next;
   ListNode(int x) {
       val = x;
       next = null;
   }
}

Java: MergeKSortedLists

public ListNode mergeKLists(ArrayList<ListNode> lists) {
   if(lists.isEmpty())
       return null;
   ArrayList<ListNode> nodes=new ArrayList<ListNode>();
   for(int i=0;i<lists.size();i++)
   {
       if(lists.get(i)!=null)
           nodes.add(lists.get(i));
   }
 
   if(nodes.isEmpty())
       return null;          
   ListNode min;      
   ListNode head=null;
   ListNode curr=head;
 
   while(!nodes.isEmpty())
   {          
       min=nodes.get(0);
       for(int i=0;i<nodes.size();i++)
       {
           if( nodes.get(i).val<=min.val)
           {                                      
               min=nodes.get(i);
           }
       }
     
       if(head==null)
       {
           head=min;
           curr=head;
       }          
     
       else
       {          
           curr.next=min;
           curr=curr.next;
       }
     
       nodes.remove(min);
       if(min.next!=null)
           nodes.add(min.next);          
   }
 
   return head;
}