Simple JAVA Nlog(K) solution with explanation


  • 2
    B

    Here is my simple nlog(k) solution where n refers the total number of nodes we have.

    The idea is that we maintain a min-heap with capacity of k elements. Since all lists are sorted, the current minimum node must be one of the top-most elements among those lists, so here we can offer all k top-most nodes into min-heap where extracting the min value is log(k) time. But each time we also have to insert a new node and the node should come from the very list we just extract a min node from! This is how we make sure the next min node is inside our heap but not somewhere in a list. I build a hash map "lookUpTable" to accomplish this step, the key is node and value is its corresponding index of input lists array, after extracting a node, we can easily trace back to the very list the node comes from.

    Because the size of min-heap is always bounded by k, and we at most extract n times, the running time would be O(nlog(k)) therefore.

    public class Solution {
     public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if(len == 0) return null;
        
        HashMap<ListNode, Integer> lookUpTable = new HashMap<>();
        PriorityQueue<ListNode> que = new PriorityQueue<>((a,b)->a.val - b.val);
        for(int i=0; i<len; i++){
            ListNode cur = lists[i];
            if(cur == null) continue;
            que.offer(cur);
            lookUpTable.put(cur, i);
        }
        
        ListNode head = null, cur = null, nextInput = null, pre = null;
        while(!que.isEmpty()){
             cur = que.poll();
             int idx = lookUpTable.get(cur);
             lookUpTable.remove(cur);
             nextInput = lists[idx].next;
             lists[idx] = nextInput;
             if(nextInput != null){
                 que.offer(nextInput);
                 lookUpTable.put(nextInput, idx);
             }
             if(head == null){
                 head = cur;
                 pre = cur;
                 continue;
             }
             pre.next = cur;
             pre = cur;
        }
        return head;
    }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.