Problem 8.9 · Linked ListsHard

Merge K Sorted Lists

PatternK-Way Merge Divide and Conquer Dummy Head and Merging

What it teaches: Scale "merge two" to k lists: a min-heap of the k fronts, or pairwise merging in rounds, both O(N log k).

Practise it on judges as “Merge k Sorted Lists”.

The problem

Given an array of k sorted linked lists, merge them into one sorted list and return it.

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]

Example 2

Input: lists = []
Output: []

Constraints

0 ≤ k ≤ 10⁴
Total nodes N ≤ 10⁴
Each list sorted

Pattern clues in the wording

→ Many sorted sequences combined
→ Always need the smallest of k fronts → min-heap

These clues point to K-Way Merge: Put the first element of each sorted list in a min-heap, repeatedly take the smallest, and push its successor.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return null;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	lists = [[1,4,5],[1,3,4],[2,6]]	[1,1,2,3,4,4,5,6]
2	lists = []	[]
3	lists = [[]]	[]

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Merge one by one · O(N · k)2. Divide and conquer: merge in rounds · O(N log k)3. Optimal: min-heap of the fronts · O(N log k)

Merge one by one

Time O(N · k) Space O(1)

Merge list 1 with list 2, the result with list 3, and so on.

Approach 1

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode result = null;
        for (ListNode l : lists) result = merge(result, l);
        return result;
    }
    private ListNode merge(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;
    }
}

Verdict: Early nodes get re-scanned in every round: slow for large k.

Divide and conquer: merge in rounds

Time O(N log k) Space O(1) extra

Merge lists in pairs (0 with 1, 2 with 3, ...), then merge the results in pairs, until one list remains. Each node takes part in about log k merges.

Approach 2

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        for (int step = 1; step < lists.length; step *= 2)
            for (int i = 0; i + step < lists.length; i += 2 * step)
                lists[i] = merge(lists[i], lists[i + step]);
        return lists[0];
    }
    private ListNode merge(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;
    }
}

Verdict: Same complexity as the heap, using only the two-list merge.

Optimal: min-heap of the fronts

Time O(N log k) Space O(k)

Put each list's head into a min-heap ordered by value. Repeatedly poll the smallest node, attach it to the result, and push its next if it exists.

Approach 3

import java.util.PriorityQueue;

class Solution {
    public ListNode mergeKLists(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 smallest = heap.poll();
            tail.next = smallest;
            tail = smallest;
            if (smallest.next != null) heap.offer(smallest.next);
        }
        return dummy.next;
    }
}

Verdict: The classic K-way merge; the Heaps module covers this pattern in depth.

Before you submit

Edge cases and common mistakes

Test these inputs

k = 0
Some lists empty
k = 1
All lists have one node

Mistakes people make

Adding null heads to the heap.
Comparator x.val - y.val (fine for small values here, but prefer Integer.compare).

Interview

Follow-up questions

Why O(N log k) and not O(N log N)?

Command Palette