Merge K Sorted Lists Visualization for Coding Interviews

By Rahul Kumar · Senior Software Engineer · Updated May 2026 · Category: Linked Lists

Min-heap merge — O(N log k).

Concept

Merging K sorted linked lists is a staple of both interview rounds and real systems, because it is the core operation behind external merge sort, log compaction, LSM-tree reads, and streaming joins. A naive approach concatenates all nodes and sorts them, which costs O(N log N) but throws away the fact that each input is already sorted. The efficient approach uses a min-heap of size K: you always know the smallest current head across all lists, and you only pay log K per node instead of log N. This drops the total cost to O(N log K), which matters once K grows large. The algorithm also generalizes cleanly. Replace ListNode with an iterator over a sorted file and you have the merge step of external sort. Replace it with a cursor over a sorted SSTable and you have the core of an LSM-tree read path.

Merge K Sorted Lists — Interactive Simulator

Runs fully client-side in your browser; no sign-up. Or open full screen →

Launch the interactive Merge K Sorted Lists visualization — animated algorithm, step-through, and live data-structure updates.

How it works

Create a PriorityQueue ordered by node.val. Seed it by pushing the head of every non-null input list. That initial seeding costs O(K log K). Then loop: poll the smallest node from the heap, append it to the output, and if that node has a successor push the successor back into the heap. Each of the N total nodes is pushed and polled exactly once, and each heap operation is O(log K) because the heap never holds more than K elements at a time. A sentinel dummy head on the output list removes the need to special-case the first append, and a tail pointer keeps appends at O(1) so you do not rewalk the output every iteration. There are two common variants. The first is divide and conquer: pair up lists and merge two at a time, halving K each round, for the same O(N log K) total cost without needing a heap. The second is the streaming variant for truly large K where you cannot hold all K heads in memory; in that case you page input cursors into the heap in batches. For interview purposes the heap-based version is the clearest, and it matches how real merge iterators are written in Lucene and RocksDB.

Implementation

mergeKLists with a PriorityQueue

import java.util.PriorityQueue;

public class MergeKLists {
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int v) { this.val = v; }
        ListNode(int v, ListNode n) { this.val = v; this.next = n; }
    }

    /** O(N log K) time, O(K) extra space for the heap. */
    public static ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        // Min-heap ordered by node value.
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));

        for (ListNode head : lists) {
            if (head != null) heap.offer(head);
        }

        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (!heap.isEmpty()) {
            ListNode smallest = heap.poll();
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) heap.offer(smallest.next);
        }

        tail.next = null; // defensive: detach any trailing cycle
        return dummy.next;
    }

    /** Divide-and-conquer alternative with the same O(N log K) bound, no heap. */
    public static ListNode mergeKListsDC(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        int interval = 1, n = lists.length;
        while (interval < n) {
            for (int i = 0; i + interval < n; i += interval * 2) {
                lists[i] = mergeTwo(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }
        return lists[0];
    }

    private static ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0), t = dummy;
        while (a != null && b != null) {
            if (a.val <= b.val) { t.next = a; a = a.next; } else { t.next = b; b = b.next; }
            t = t.next;
        }
        t.next = (a != null) ? a : b;
        return dummy.next;
    }
}

Complexity

Time: O(N log K), where N is total nodes and K is number of lists
Space: O(K) for the heap; output reuses input nodes

Common pitfalls

Pushing null heads into the heap throws NullPointerException on compare
Using a max-heap by accident and getting the output reversed
Forgetting to push smallest.next after polling, which drops the rest of that list
Allocating new nodes during merge doubles memory; splicing existing nodes is enough
Not handling the empty input array, returning a dummy node instead of null
Assuming inputs are sorted when they are not; the heap-merge algorithm requires sorted inputs

Key design decisions & trade-offs

Algorithm choice — Chosen: Heap of K heads. O(N log K) and easy to reason about; generalizes to streaming merges of sorted files or SSTables
Heap vs divide-and-conquer — Chosen: Heap for clarity, D&C when heap allocation is a concern. Same asymptotic cost; D&C has lower constant factors and no priority queue allocation
Node reuse — Chosen: Splice existing nodes into output. Avoids O(N) extra allocations; the inputs are typically consumed anyway

Practice problems

Merge k Sorted Lists

Interview follow-ups

Adapt the algorithm to merge K sorted arrays instead of linked lists
Merge K sorted streams that do not fit in memory (external merge sort)
Find the smallest range that includes at least one element from each of K lists
Kth smallest element across K sorted lists
Merge K sorted files during LSM-tree compaction

Why it matters

Merge K Sorted Lists is a core part of the Linked Lists toolkit. If you are preparing for a technical interview at a top-tier company or teaching a course, a working visualization is the fastest path from "I read about it" to "I understand it".