LeetCode 23 – Merge k Sorted Lists

Merge k Sorted Lists is Merge Two Sorted Lists with the interesting part added back. Merging two is a solved problem; the question here is in what order you merge them, and the naive order costs a factor of k. Two good answers exist and they have different space profiles, which is what makes this a real interview question.

The problem

Given an array of k sorted linked lists, merge them all into one sorted list.

Input:  [1 -> 4 -> 5,  1 -> 3 -> 4,  2 -> 6]
Output:  1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Input:  []          Output: (empty)
Input:  [(empty)]   Output: (empty)   — a list in the array may itself be null

That last case is the input everyone forgets. The array is non-null but an entry inside it can be null, and both solutions below have to survive it.

Why the obvious order is the wrong one

Merge list 1 into list 2, then merge the result into list 3, and so on. It is correct, and it is O(N·k) where N is the total number of nodes.

The reason is that the accumulator keeps getting re-walked. After i merges it holds roughly i·N/k nodes, and merging the next list traverses all of them again. Summing over i from 1 to k gives O(N·k) — with 10,000 lists, every node is touched about 10,000 times.

The fix is to stop merging one list into a growing giant, and instead merge in pairs: k lists become k/2, then k/4, down to one. Each node is still copied once per level, but there are only log k levels. O(N log k).

L1  L2   L3  L4   L5  L6   L7  L8      k = 8
  \/       \/       \/       \/
  A        B        C        D          level 1: every node touched once
    \     /           \     /
      AB                 CD             level 2: every node touched once
         \             /
            ABCDEFGH                    level 3
                                        3 = log2(8) levels -> O(N log k)

Divide and conquer

Recursion expresses the pairing naturally: split the array in half, merge each half, then merge the two results with the two-list routine.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;
        return merge(lists, 0, lists.length - 1);
    }

    private ListNode merge(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];         // may be null — that is fine

        int mid = lo + (hi - lo) / 2;           // not (lo + hi) / 2: that can overflow
        return mergeTwo(merge(lists, lo, mid), merge(lists, mid + 1, hi));
    }

    private ListNode mergeTwo(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (a != null && b != null) {
            if (a.val <= b.val) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }

        tail.next = (a != null) ? a : b;
        return dummy.next;
    }
}

A null entry in the array needs no guard at all: merge returns it as-is at the base case, and mergeTwo already handles a null argument by splicing the other side on. The empty-array check at the top is the only special case, and it is there because merge(lists, 0, -1) would be nonsense.

lo + (hi - lo) / 2 rather than (lo + hi) / 2 is the standard overflow-safe midpoint. It cannot matter at these array sizes, and writing it correctly by habit is worth more than the one time it does.

Python

class Solution:
    def mergeKLists(self, lists: list[ListNode]) -> ListNode:
        if not lists:
            return None
        return self._merge_range(lists, 0, len(lists) - 1)

    def _merge_range(self, lists, lo: int, hi: int):
        if lo == hi:
            return lists[lo]

        mid = (lo + hi) // 2
        return self._merge_two(self._merge_range(lists, lo, mid),
                               self._merge_range(lists, mid + 1, hi))

    def _merge_two(self, a, b):
        dummy = tail = ListNode(0)

        while a and b:
            if a.val <= b.val:
                tail.next = a
                a = a.next
            else:
                tail.next = b
                b = b.next
            tail = tail.next

        tail.next = a or b
        return dummy.next

Python integers do not overflow, so (lo + hi) // 2 is genuinely safe here — the defensive form is a Java habit, not a universal one.

The heap alternative

The other O(N log k) answer keeps the current head of every list in a min-heap. Pop the smallest, append it, and push its successor. The heap never holds more than k nodes, so each of the N pops costs O(log k).

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq =
        new PriorityQueue<>(Comparator.comparingInt(node -> node.val));

    for (ListNode node : lists) {
        if (node != null) pq.offer(node);   // null lists must be skipped, not offered
    }

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

Here the null check is mandatory — pq.offer(null) throws a NullPointerException, and the comparator would dereference it anyway.

In Python, heapq compares tuples element by element and falls through to the next element on a tie. A ListNode is not orderable, so (node.val, node) raises TypeError the moment two nodes share a value — which the sample input [1 -> 4 -> 5, 1 -> 3 -> 4] does immediately. Push (node.val, i, node) with a unique tiebreaker.

Which to write

Divide and conquer wins on space, O(log k) against O(k), and it needs no library type. Write that one. The heap has the better story for the follow-up though — if the lists arrive as k streams too large to hold in memory, only the heap version works, because it only ever holds one node per stream and never needs random access to the array. Say that; it is usually the question after this one.

What the interviewer is checking

• That you know sequential merging is O(N·k) and can explain where the extra factor comes from.
• That you reach for pairwise merging or a heap, and can argue O(N log k).
• An empty array, and a null entry inside a non-empty array.
• That the heap version skips nulls rather than offering them.
• That you can compare the two good solutions on space, not just parrot that both are O(N log k).