Simple JAVA Nlog(K) solution with explanation

  • 2

    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;
            lookUpTable.put(cur, i);
        ListNode head = null, cur = null, nextInput = null, pre = null;
             cur = que.poll();
             int idx = lookUpTable.get(cur);
             nextInput = lists[idx].next;
             lists[idx] = nextInput;
             if(nextInput != null){
                 lookUpTable.put(nextInput, idx);
             if(head == null){
                 head = cur;
                 pre = cur;
    = 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.