#23 Merge k Sorted Lists

Hardsolve on LeetCode ↗

frequently reported atNVIDIA Meta Oracle Amazon ByteDance / TikTok Apple

the problem

In plain words

Merge k sorted linked lists into one sorted linked list and return its head.

in lists = [[1,4,5],[1,3,4],[2,6]]

out [1,1,2,3,4,4,5,6]

in lists = []

out []

in lists = [[]]

out []

0 ≤ k ≤ 10⁴
0 ≤ lists[i].length ≤ 500
-10⁴ ≤ value ≤ 10⁴
Each list is sorted; total nodes ≤ 10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternK-way merge Divide and conquer

The next node of the result is always the smallest of the k current heads. A min-heap of the k heads finds it in O(log k).

solutions

From brute force to optimal

Dump all values in a list, sort, rebuild.

Walk all lists into an ArrayList.
Sort.
Build a new list.

timeO(N log N)

N = total nodes; ignores that the lists were already sorted.

spaceO(N)

Values plus new nodes.

javajava.util.*

1class Solution {2    public ListNode mergeKLists(ListNode[] lists) {3        List<Integer> all = new ArrayList<>();4        for (ListNode head : lists) for (ListNode n = head; n != null; n = n.next) all.add(n.val);5        Collections.sort(all);6        ListNode dummy = new ListNode(0), tail = dummy;7        for (int v : all) tail = tail.next = new ListNode(v);8        return dummy.next;9    }10}

result = merge(result, list) for each list.

Two-list merge from the linked-lists chapter.
Fold it over all k lists.

timeO(k·N)

The growing result is re-walked k times.

spaceO(1)

Relinks existing nodes.

javajava.util.*

1class Solution {2    public ListNode mergeKLists(ListNode[] lists) {3        ListNode merged = null;4        for (ListNode list : lists) merged = merge(merged, list);   // the result keeps growing5        return merged;6    }7 8    static ListNode merge(ListNode a, ListNode b) {9        ListNode dummy = new ListNode(0), tail = dummy;10        while (a != null && b != null) {11            if (a.val <= b.val) { tail.next = a; a = a.next; }12            else { tail.next = b; b = b.next; }13            tail = tail.next;14        }15        tail.next = a != null ? a : b;16        return dummy.next;17    }18}

Poll the smallest head, append it, offer its next node.

Offer every non-null head.
Poll → append to the tail.
If it has a next, offer that.

timeO(N log k)

Every node is offered and polled once on a heap of ≤ k.

spaceO(k)

The heap holds one node per list.

javajava.util.*

1class Solution {2    public ListNode mergeKLists(ListNode[] lists) {3        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));4        for (ListNode head : lists) if (head != null) heap.offer(head);   // one candidate per list5        ListNode dummy = new ListNode(0), tail = dummy;6        while (!heap.isEmpty()) {7            ListNode smallest = heap.poll();          // smallest of all current heads8            tail = tail.next = smallest;9            if (smallest.next != null) heap.offer(smallest.next);   // its list's next candidate10        }11        return dummy.next;12    }13}

sim

Dry run

loading simulation…

javajava.util.*

1class Solution {2    public ListNode mergeKLists(ListNode[] lists) {3        PriorityQueue<ListNode> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n.val));4        for (ListNode head : lists) if (head != null) heap.offer(head);   // one candidate per list5        ListNode dummy = new ListNode(0), tail = dummy;6        while (!heap.isEmpty()) {7            ListNode smallest = heap.poll();          // smallest of all current heads8            tail = tail.next = smallest;9            if (smallest.next != null) heap.offer(smallest.next);   // its list's next candidate10        }11        return dummy.next;12    }13}

Merge lists in pairs: k → k/2 → k/4 … → 1.

gap = 1, 2, 4, …
Merge lists[i] with lists[i + gap].

timeO(N log k)

log k rounds, each touching every node once.

spaceO(1)

Iterative, relinks nodes in place.

javajava.util.*

1class Solution {2    public ListNode mergeKLists(ListNode[] lists) {3        if (lists.length == 0) return null;4        for (int gap = 1; gap < lists.length; gap *= 2) {           // pair up lists: 1+1, 2+2, 4+4…5            for (int i = 0; i + gap < lists.length; i += 2 * gap) {6                lists[i] = merge(lists[i], lists[i + gap]);7            }8        }9        return lists[0];10    }11 12    private static ListNode merge(ListNode a, ListNode b) {        // the classic two-list merge13        ListNode dummy = new ListNode(0), tail = dummy;14        while (a != null && b != null) {15            if (a.val <= b.val) { tail.next = a; a = a.next; }16            else { tail.next = b; b = b.next; }17            tail = tail.next;18        }19        tail.next = a != null ? a : b;20        return dummy.next;21    }22}

in the room

How to say it in the interview

talk track

Start from merging two lists, then ask: how do I pick the smallest of k heads fast? → heap.
Mention divide and conquer as the O(1)-space alternative.

traps

Offering null heads (empty lists) — PriorityQueue throws on null.
Comparator (a, b) -> a.val - b.val — fine for these bounds, but prefer comparingInt.

what they ask next

Follow-ups

Kth Smallest Element in a Sorted Matrix (LC 378)?

Same k-way merge: rows are sorted lists; poll k times from a heap of row cursors.

before you submit

Edge cases to test

lists = [] or lists = [[]]: return null.
Empty lists mixed in: never offer null — PriorityQueue throws NullPointerException.
Equal values from different lists may come out in either order; both are correct.

practise next