[LeetCode] 23. Merge k Sorted Lists

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

Subscribe to see which companies asked this question

1. Use priority queue, organize ListNodes at head of all queues.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    class ListNodeComp implements Comparator{
        @Override
        // has to be public
        public int compare(ListNode a, ListNode b){
            return a.val - b.val;
        }
    }
    
    public ListNode mergeKLists(ListNode[] lists) {
        
        int k = lists.length;
        
        if(0 == k)
            return null;
            
        ListNode resPreHead = new ListNode(0);
        
        ListNode index = resPreHead;
        
        PriorityQueue pq = new PriorityQueue(k, new ListNodeComp());
        
        for(int i = 0; i < k; ++i){
            
            if(null != lists[i]){
                pq.add(lists[i]);
            }
            
        }
        
        while(null != pq.peek()){
            
            index.next = pq.poll();
            index = index.next;
            
            if(null != index.next){
                pq.add(index.next);
                // be safe
                index.next = null;
            }
            
        }
        
        // log(k)*n
        
        // k/2*(n/k)*2 = n
        
        // log(k) times 
        
        return resPreHead.next;
    }
}