Merge K Sorted Lists

HARD✓ CHIP-TIMEDLC #23 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

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 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

THE HINTS — TAKE 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 BOARD — THE 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 SPLITS — TWO 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-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED