Merge K Sorted Lists

The briefingthe full drill, in my own words

The drill: Merge k already-sorted linked lists into one fully sorted list, splicing the existing nodes together instead of building a fresh one from scratch.

A collection of k linked lists arrives, each one already sorted in ascending order on its own. The job is to weave them into a single linked list that is sorted across all of them combined.

The result should be built from the existing nodes themselves — relinking them into one chain — rather than manufacturing a brand-new set of nodes from scratch.

Any of the k lists may be empty, and the whole collection may be empty too; the merged result in those cases is simply whatever nodes remain, possibly none at all.

the number of lists can range from zero up to a few thousand
each individual list is already sorted ascending
node values can be negative, zero, or positive
the answer reuses the input nodes rather than allocating new ones

EX 01

lists = [[2, 6, 9], [1, 5, 8], [0, 7]]

→ [0, 1, 2, 5, 6, 7, 8, 9]

three interleaved lists

EX 02

lists = []

→ []

no lists at all

EX 03

lists = [[]]

→ []

a single empty list

The hintstake only what you need

HINT 1 THE NUDGE

Merging two sorted lists is one clean walk with two pointers — folding k lists together the same way, list by list, means the front runs get re-merged again on every later list. What keeps getting paid for over and over?

HINT 2 THE STRUCTURE

At any moment the only thing that matters is: which of the k current heads is smallest. That's a repeated 'minimum among k candidates' question — a structure that tracks a running minimum turns an O(k) scan into something faster.

HINT 3 ONE STEP FROM THE ANSWER

Push all k heads into a min-heap keyed by value. Pop the smallest, attach it to the result, and if that node has a next, push that back in. Repeat until the heap is empty.

Coach's boardthe pattern, step by step

THE MIN-HEAP MERGEPATTERN · MIN-HEAP OF HEADSlists = [[2,6,9], [1,5,8], [0,7]]

STEP 1

Merge three sorted lists — [2,6,9], [1,5,8], [0,7] — with a min-heap holding the k current heads: 2, 1, and 0.

STEP 1 / 10 · ← → WORK TOO

The splitstwo paces, two languages

grind/merge-k-sorted-lists.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))  # i breaks ties, never compares nodes

        dummy = ListNode()
        tail = dummy
        while heap:
            _, i, node = heapq.heappop(heap)
            tail.next = node
            tail = tail.next
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))
        return dummy.next

TIME O(N LOG K)SPACE O(K)PYTHON · RACE PACE · 16 LN

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        vals = []
        for head in lists:
            node = head
            while node:
                vals.append(node.val)
                node = node.next
        vals.sort()  # ignores that k of the runs were already sorted

        dummy = ListNode()
        tail = dummy
        for v in vals:
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

TIME O(N LOG N)SPACE O(N)PYTHON · TRAINING PACE · 16 LN

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }

        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll();
            tail.next = node;
            tail = tail.next;
            if (node.next != null) {
                heap.offer(node.next);
            }
        }
        return dummy.next;
    }
}

TIME O(N LOG K)SPACE O(K)JAVA · RACE PACE · 22 LN

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> vals = new ArrayList<>();
        for (ListNode head : lists) {
            for (ListNode n = head; n != null; n = n.next) {
                vals.add(n.val);
            }
        }
        Collections.sort(vals); // ignores that k of the runs were already sorted

        ListNode dummy = new ListNode();
        ListNode tail = dummy;
        for (int v : vals) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

TIME O(N LOG N)SPACE O(N)JAVA · TRAINING PACE · 19 LN

✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED