Merge k Sorted Lists (LeetCode Linked List)

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

Idea: I tried to make use of merge 2 sorted linked lists. However it gets exceed time limits error in Java. So I have to use heap sort. First insert all the heads of the lists to the heap. Pop the root of the heap and insert the root's next to the heap, until the heap becomes empty.

Time: O(n^2lgn) Space: O(n). Assume we have n lists each of which has n elements.

Code:

 public class Solution {  
   public Comparator<ListNode> comp=new Comparator<ListNode>()  
   {  
     public int compare(ListNode left,ListNode right)  
     {  
       if(left==null)  
         return 1;  
       else if(right==null)  
         return -1;  
       else  
         return left.val-right.val;  
     }  
   };  
   public ListNode mergeKLists(List<ListNode> lists) {  
     if(lists.size()==0)   
       return null;  
     Queue<ListNode> heap=new PriorityQueue<ListNode>(lists.size(),comp);  
     for(ListNode head:lists)  
     {  
       if(head!=null)  
         heap.add(head);  
     }  
     ListNode dummy=new ListNode(0);  
     ListNode tail=dummy;  
     while(!heap.isEmpty())  
     {  
       ListNode tmp=heap.poll();  
       tail.next=tmp;  
       tail=tail.next;  
       if(tmp.next!=null)  
         heap.add(tmp.next);  
     }  
     return dummy.next;  
   }  
 }