☕ DSA Java Articles

Topics › Heaps › Medium Problems

Merge K sorted Lists

Hard TUF ID 569 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array of k singly linked lists, each sorted in non-decreasing order. Merge them into one sorted linked list and return its head. Some lists may be empty (null), and the array itself may be empty.

Constraints: 0 ≤ k ≤ 10^4, total number of nodes N up to about 10^5, values fit in an int. Below, N always means the total number of nodes across all lists.

The node type is the usual one:

static class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Example 1

lists = [1 -> 4 -> 5, 1 -> 3 -> 4, 2 -> 6]
answer = 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Example 2

lists = [] or [null]
answer = null            // nothing to merge

Approach 1: Brute force, collect and sort

Intuition. Forget that the lists are sorted. Pour every value into one array list, sort it, and build a brand-new linked list from the sorted values. It is correct by construction and ignores the structure entirely, which is why it is slower than it needs to be.

Algorithm.

  1. Walk every list and append every value to values.
  2. Sort values.
  3. Build a new list from them, using a dummy head to avoid a special case for the first node.
static ListNode bruteForce(ListNode[] lists) {
    List<Integer> values = new ArrayList<>();
    for (ListNode head : lists) {
        for (ListNode cur = head; cur != null; cur = cur.next) values.add(cur.val);
    }
    Collections.sort(values);
    ListNode dummy = new ListNode(0), tail = dummy;
    for (int v : values) {
        tail.next = new ListNode(v);
        tail = tail.next;
    }
    return dummy.next;
}

Complexity. Time O(N log N) for the sort; collecting and rebuilding are O(N). Space O(N) for the values and the new nodes.

Approach 2: Better, merge the lists one at a time

Intuition. Merging two sorted lists is a classic linear-time operation: compare the two fronts, take the smaller, advance. Merge list 0 with list 1, then merge the result with list 2, and so on. This uses the sortedness and needs no extra memory, because it relinks existing nodes.

The merge helper takes nodes in order and stitches them behind a dummy tail. Using <= takes from the left list on ties, which keeps equal values in their original list order (a stable merge).

static ListNode mergeTwo(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), 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;
}

Algorithm.

  1. Start with result = null.
  2. For each list head, set result = mergeTwo(result, head).
static ListNode better(ListNode[] lists) {
    ListNode result = null;
    for (ListNode head : lists) result = mergeTwo(result, head);
    return result;
}

Complexity. Time O(N k) in the worst case. The problem is the growing result: it is re-walked during every later merge. With k lists of N / k nodes, the i-th merge touches about i × N / k nodes, and summing over i gives roughly N k / 2. Space O(1) extra.

Approach 3: Optimal, min-heap of the list fronts

Intuition. At any moment the next node of the answer is the smallest among the current front nodes of the k lists, since every list is sorted and nothing behind a front can be smaller than that front. So we need a structure that holds k candidates and repeatedly hands out the smallest: a min-heap. After taking a node from the heap, the only new candidate is that node’s successor in its own list, so we push just that one.

Algorithm.

  1. Push the head of every non-empty list into a min-heap ordered by val.
  2. While the heap is not empty: pop the smallest node, append it to the result, and if it has a next, push next.
  3. Return dummy.next.
static ListNode optimalHeap(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode head : lists) {
        if (head != null) heap.offer(head);
    }
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.poll();
        tail.next = node;
        tail = node;
        if (node.next != null) heap.offer(node.next);
    }
    return dummy.next;
}

Dry run on Example 1 (heap shown as values; subscripts tell the lists apart):

step heap before pop popped pushed result so far
1 {1a, 1b, 2c} 1a 4a 1
2 {1b, 2c, 4a} 1b 3b 1 1
3 {2c, 3b, 4a} 2c 6c 1 1 2
4 {3b, 4a, 6c} 3b 4b 1 1 2 3
5 {4a, 4b, 6c} 4a 5a 1 1 2 3 4
6 {4b, 5a, 6c} 4b none 1 1 2 3 4 4
7 {5a, 6c} 5a none … 5
8 {6c} 6c none … 6

When two fronts hold equal values (steps 1 and 5), either may come out first; the merged values are the same.

Complexity. Time O(N log k): each node is pushed and popped once on a heap of at most k nodes. Space O(k) for the heap; the nodes themselves are reused. The last node popped always has next == null (otherwise its successor would still be in the heap), so the result is properly terminated without extra code.

Approach 4: Optimal alternative, divide and conquer

Intuition. Approach 2 was slow only because it merged in a lopsided order: one ever-growing list against small ones. Merge in a balanced order instead, like the merge phase of merge sort: pair up lists (0, 1), (2, 3), ..., then pair up the results, halving the number of lists each round. Every node takes part in one merge per round, and there are log2 k rounds.

Algorithm.

  1. If there are no lists, return null. Copy the array of heads into work.
  2. For step = 1, 2, 4, ... while step < k: for every i that is a multiple of 2 × step with i + step < k, set work[i] = mergeTwo(work[i], work[i + step]).
  3. Return work[0].
static ListNode optimalDivideAndConquer(ListNode[] lists) {
    if (lists.length == 0) return null;
    ListNode[] work = lists.clone();
    for (int step = 1; step < work.length; step *= 2) {
        for (int i = 0; i + step < work.length; i += 2 * step) {
            work[i] = mergeTwo(work[i], work[i + step]);
        }
    }
    return work[0];
}

Complexity. Time O(N log k): each of the log2 k rounds touches every node at most once. Space O(k) for the copy of the head array (overwrite the input array instead to make it O(1)), and no recursion, so there is no stack depth to worry about.

Both optimal versions have the same bound. The heap version is the natural one when the lists arrive as streams and must be consumed lazily; the divide-and-conquer version does its comparisons inside plain sequential merges with no heap bookkeeping, which tends to be faster in practice.

Edge cases and pitfalls