Merge K Sorted Lists - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const INCLUDED = 'current', INCLUDED_COLOR = 'blue';
const WILL_BE_DEQUEUED_COLOR = 'red';

function visMainFunction(inputLists) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    const lists = convertInput(inputLists);

    startBatch();
    // dummy stays just for easy head handling in the merged list view
    const dummy = new ListNode("Dummy");
    const mergedList = new VisLinkedList(dummy, { dataPropName: 'val' });
    mergedList.makeVisManagerForNode(dummy).addClass(INCLUDED)

    VisListManager.createVisForAll(lists);

    // Note: PriorityQueue implementation used by leetcode accepts the priority as new MinPriorityQueue((node) => node.val)
    const heap = new VisMinPriorityQueue({
        priority: node => node.val
    }).options({
        labelExtractionPolicy: node => `${node.val}`
    });

    for (let i = 0; i < lists.length; i++) {
        if (lists[i]) heap.enqueue(lists[i]);
    }
    endBatch();
    
    let current = dummy;

    notification(`
        ✅ <b>Initialization complete.</b><br><br>
        We created a <b>dummy node</b> and a <b>current pointer</b> to help build the merged list efficiently.<br><br>
        The <b>dummy node</b> acts as a fixed anchor at the start of the merged list — it does not hold meaningful data, but it simplifies
        the logic for attaching new nodes since we never have to handle a special “head” case separately.<br>
        The <b>current pointer</b> always points to the last node in the merged list, and we’ll advance it as we attach new nodes.<br><br>
        Once the merging process is complete, the real merged list begins right after the dummy node, 
        so we’ll simply return <code>dummy.next</code> as the final result.<br><br>

        MinHeap initialized as well.<br>
        We pushed the <b>head node of each non-empty list</b> into the heap.<br><br>
        Since each list is already sorted, these head nodes represent the <b>smallest (first unprocessed) nodes</b> 
        from their respective lists.<br><br>
        The heap therefore always contains the <b>current minimum candidates</b> from all lists, 
        and its top (smallest value) node is the <b>globally smallest remaining node</b> across all lists.
    `);

    notification(`
        📌 Starting merge process.<br>
        We'll repeatedly take the <b>smallest node</b> from the heap, append it to the merged list,
        and then (if that node had a <code>.next</code>) push that <code>.next</code> back into the heap.<br><br>
        This way, the heap always represents the current “frontier” of all lists.
    `);

    while (!heap.isEmpty()) {
        startPartialBatch();

        // take the smallest actual node
        const smallestNode = heap.front().element;
        VisListManager.markBeforeDequeue(smallestNode);
        notification(`
            📤 Will call the <code>dequeue()</code> operation to ${makeColoredSpan('remove and get the next smallest node', WILL_BE_DEQUEUED_COLOR)} — the node with value <b>${smallestNode.val}</b>.<br><br>
            This node is currently at the <b>front of the MinHeap</b>, meaning it’s the <b>globally smallest</b> among all remaining nodes.<br><br>
            <code>dequeue()</code> operation remove it from the heap and then we will attach it to the merged list. 
            Although the merged list only needs the node’s value, it’s perfectly fine to attach the whole node since,
            as we continue merging, every node will naturally fall into its correct sorted position.
        `);

        heap.dequeue();

        current.next = smallestNode;
        current = current.next;
        current && mergedList.makeVisManagerForNode(current).addClass(INCLUDED);

        // if that node has a next, push that next node into the heap
        if (smallestNode.next) {
            notification(`
                📥 Advancing that list.<br>
                The smallest node we just attached came from one of the input lists. 
                Its <code>next</code> node (${smallestNode.next.val}) is now the <b>only remaining candidate</b> 
                from that list that could possibly become the smallest among all unprocessed nodes.<br><br>
                Therefore, we push it into the MinHeap so it can compete with the <b>current smallest (first unprocessed) nodes</b> 
                from the other lists for the next merge position.
            `);
            heap.enqueue(smallestNode.next);
            VisListManager.destroyVis(smallestNode);
            VisListManager.createVis(smallestNode.next);
        }

        endBatch();
    }

    notification(`
        🏁 <b>Merging complete!</b><br>
        All input lists have been fully processed, and every node has been linked in sorted order.<br><br>
        The merged list starts right after the <b>dummy node</b>, so we return <code>dummy.next</code> as the head of the final merged linked list.
    `);

    return dummy.next;
}

function convertInput(inputLists) {
    return inputLists.map(arr => {
        let dummy = new ListNode(0);
        let current = dummy;
        for (let val of arr) {
            current.next = new ListNode(val);
            current = current.next;
        }
        return dummy.next;
    });
}

class VisListManager {
    static rootToVisList = new Map();

    static createVis(root) {
        this.rootToVisList.set(
            root,
            new VisLinkedList(root, { dataPropName: 'val' }).createVis(true)
        );
    }

    static destroyVis(root) {
        this.rootToVisList.get(root).destroyVis();
    }

    static markBeforeDequeue(root) {
        this.rootToVisList.get(root).visManager.setProp('borderColor', WILL_BE_DEQUEUED_COLOR);
    }

    static createVisForAll(roots) {
        roots.forEach(root => {
            root && this.createVis(root);
        });
    }
}

// Definition for singly-linked list (matching LeetCode's definition).
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Color Schema</b><br><br>
        🟦 <b>${makeColoredSpan('Merged nodes', INCLUDED_COLOR)}</b> — all nodes that have already been placed to their correct place in the merged list so far; the last of such nodes is the current node.<br>
        🔴 <b>${makeColoredSpan('Next smallest node (to be dequeued)', WILL_BE_DEQUEUED_COLOR)}</b> — the node currently at the front of the MinHeap that is about to be removed and placed in the merged list.
    `);
}

function initClassProperties() {
    setClassProperties(INCLUDED, { backgroundColor: INCLUDED_COLOR });
}

Approach

We are given multiple sorted linked lists and we want to merge them into one fully sorted linked list. The main challenge is to always know which node among all lists should come next in sorted order.

The key idea is to always pull the globally smallest available node, append it to the merged list, and then advance only the list that node came from. We do this efficiently using a MinHeap.

We also maintain a temporary dummy node at the start of the result list. The dummy node is just a placeholder node whose .next will point to the true head of the merged list. We keep a current pointer that always points to the last node we've attached so far. At the end, we simply return dummy.next as the head of the merged list (and we ignore the dummy itself).

High-Level Strategy

Step 1: Initialize the MinHeap with the head of each list.
We create a MinHeap whose priority is based on node.val. Then, for each non-empty list, we push that list’s head node into the heap.

Because each input list is already sorted, its head node is the smallest node that list can currently offer. That means at this moment, the heap contains exactly the smallest (first unprocessed) node from each list.

The MinHeap is therefore storing all current “candidates,” and the node at the top of the heap is the globally smallest remaining node across all lists.
Step 2: Build the merged list by repeatedly taking the smallest node.
We maintain a dummy node and a current pointer, which walks along the output list we are building.

While the heap is not empty:
- Dequeue the front of the MinHeap as smallestNode. This node is the smallest among all nodes that are still unmerged.
- Append smallestNode to the merged list by doing current.next = smallestNode, then advance the current pointer by doing current = current.next.
- If smallestNode had a .next, we push that .next node into the MinHeap so it can compete for the next merge position.
Why only .next?
Because once we pull a node from some list, the only remaining candidate from that list that could possibly compete to be the next smallest is exactly that node’s .next — the lists are individually sorted, so nothing earlier in that list remains unprocessed, and nothing later in that list can be smaller than .next.
Repeat until the heap is empty.
Each loop extracts the globally smallest node and attaches it in order. When the heap is finally empty, it means we have consumed every node from every list and connected them (in ascending order) into a single merged chain starting at dummy.next.

Why this Works

The heap always holds the best next choice:
At any point, the heap contains at most one “active” node per list: the first not-yet-merged node of that list. Taking the minimum from that set guarantees we always choose the globally smallest available value next.
We advance lists lazily:
When we take a node from a given list, we don’t immediately dump the rest of that list into the heap. We only push node.next. That keeps the heap as small as possible (at most one node per list at a time, plus any nodes that became .next after merges).
We attach original nodes directly (no cloning):
Instead of creating new nodes and copying values, we reuse the actual nodes from the input lists. Each time we pop the smallest node from the heap, we attach that exact node after current in the merged list.

While we are building the merged list, the node we just attached may still have its original .next pointer into the remainder of its source list. That’s fine: as the algorithm continues, those remaining nodes will be placed in their correct positions, and by the end, the tail of the merged list will naturally point to null.
The dummy node simplifies head handling:
Using a dummy node means we don't have to treat "attach the very first node" as a special case. We always attach to current.next, update current, and keep going. At the end we just return dummy.next, which is the real head of the merged list.

Time Complexity

Let k be the number of input lists, and let N be the total number of nodes across all lists combined.

We insert each node into the MinHeap once and remove it once. Each heap operation (enqueue/dequeue) costs O(log k), since the heap holds at most one candidate per list at a time. Doing this for all N nodes across all lists gives O(N log k).

Space Complexity

Let k be the number of input lists, and let N be the total number of nodes across all lists combined.

Even though the final merged list has N nodes linked together, those nodes (and their existing .next pointers) come directly from the input lists. We only rewired those pointers — we did not allocate any new nodes or new pointer fields for them.

The only additional data structure we maintain is the MinHeap, which can hold up to k node references at once. That’s O(k) extra space, plus a few temporary pointers like dummy and current (O(1)).

Therefore, the overall auxiliary space usage of the algorithm is O(k).

Input-1

Merge K Sorted Lists - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

High-Level Strategy

Why this Works

Time Complexity

Space Complexity