44.Merge K Sorted Lists

HardBlind 75Linked List · 10/11

Problem

You are given an array of k linked lists lists, each sorted in ascending order.

Merge all of them into one sorted linked list and return its head.

Examples

Input:  lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: All values from the three sorted lists, merged in order.

Input:  lists = []
Output: []

Input:  lists = [[]]
Output: []
Explanation: One list, and it is empty.

Constraints

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10^4.

💡 Key Insight

Let N be the total number of nodes. Merging lists one at a time re-walks the growing result k times (O(kN)). To get O(N log k), either keep the k current heads in a min-heap (each pop/push costs O(log k)), or merge lists in pairs like merge sort — each round halves the number of lists, so there are only log k rounds and each touches every node once.

Brute Force (Collect and Sort)

TimeO(N log N)SpaceO(N)

Intuition

Throw every value into one array, sort it, and build a fresh list. It ignores that the inputs are sorted.

Algorithm

Walk every list, adding each val to values.
Sort values.
Build a new list from the sorted values with a dummy head.

Visualization

[1,4,5] [1,3,4] [2,6]
collect: [1,4,5,1,3,4,2,6]
sort:    [1,1,2,3,4,4,5,6] -> build list

Code

java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        List<Integer> values = new ArrayList<>();
        for (ListNode list : lists) {
            for (ListNode n = list; n != null; n = n.next) {
                values.add(n.val);
            }
        }
        Collections.sort(values);
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        for (int v : values) {
            tail.next = new ListNode(v);
            tail = tail.next;
        }
        return dummy.next;
    }
}

Complexity

Time: O(N log N) — sorting all values.
Space: O(N) — the values array and the new list.

Merge One by One

TimeO(k · N)SpaceO(1)

Intuition

Reuse the two-list merge: merge lists[0] with lists[1], then merge that result with lists[2], and so on. Correct, but the early nodes get walked again in every merge.

Algorithm

result = null.
For each list, result = mergeTwo(result, list).
Return result.

Visualization

result = []
merge with [1,4,5] -> [1,4,5]
merge with [1,3,4] -> [1,1,3,4,4,5]           (walks 6 nodes)
merge with [2,6]   -> [1,1,2,3,4,4,5,6]       (walks 8 nodes)

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode result = null;
        for (ListNode list : lists) {
            result = mergeTwo(result, list);
        }
        return result;
    }

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

Complexity

Time: O(k · N) — the accumulated result (up to N nodes) is re-walked in each of the k merges.
Space: O(1) — nodes are relinked in place.

Min-Heap

TimeO(N log k)SpaceO(k)

Intuition

The next node of the answer is always the smallest among the k current heads. A min-heap keyed by val gives that smallest head in O(log k); after taking it, push its next so the heap always holds at most one node per list.

Algorithm

Push every non-null head into a PriorityQueue ordered by val.
While the heap is non-empty:
- Pop node, append it to the result.
- If node.next != null, push it.
Return dummy.next.

Visualization

heap {1a, 1b, 2}       pop 1a, push 4a   result: 1
heap {1b, 2, 4a}       pop 1b, push 3b   result: 1,1
heap {2, 3b, 4a}       pop 2,  push 6c   result: 1,1,2
heap {3b, 4a, 6c}      pop 3b, push 4b   result: 1,1,2,3
... continue until the heap is empty

Code

java

import java.util.PriorityQueue;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
        for (ListNode head : lists) {
            if (head != null) {
                heap.offer(head);
            }
        }
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (!heap.isEmpty()) {
            ListNode node = heap.poll(); // smallest current head
            tail.next = node;
            tail = node;
            if (node.next != null) {
                heap.offer(node.next);   // its successor becomes a candidate
            }
        }
        return dummy.next;
    }
}

Complexity

Time: O(N log k) — each of the N nodes is pushed and popped once on a heap of size at most k.
Space: O(k) — the heap.

Divide and ConquerOptimal

TimeO(N log k)SpaceO(1)

Intuition

Merge lists in pairs, like the merge step of merge sort: (0,1), (2,3), … in round one, then pair up the results, until one list remains. Every round touches each node once, and there are log k rounds — so O(N log k) time with only O(1) extra space when done iteratively.

Algorithm

If lists is empty, return null.
interval = 1. While interval < k:
- For i = 0; i + interval < k; i += 2 * interval: lists[i] = mergeTwo(lists[i], lists[i + interval]).
- interval *= 2.
Return lists[0].

Dry Run

flowchart TD
    A["L0 = 1,4,5"] --> M1["merge L0+L1<br/>1,1,3,4,4,5"]
    B["L1 = 1,3,4"] --> M1
    C["L2 = 2,6"] -->|"no partner in round 1"| F["round 2: merge L0+L2<br/>1,1,2,3,4,4,5,6"]
    M1 --> F

With k = 3: round one (interval = 1) merges (0,1); L2 has no partner (2 + 1 is not < 3) and waits. Round two (interval = 2) merges (0,2). That is ceil(log2(3)) = 2 rounds.

Code

java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int k = lists.length;
        if (k == 0) {
            return null;
        }
        // Bottom-up pairwise merging: interval = 1, 2, 4, ...
        for (int interval = 1; interval < k; interval *= 2) {
            for (int i = 0; i + interval < k; i += 2 * interval) {
                lists[i] = mergeTwo(lists[i], lists[i + interval]);
            }
        }
        return lists[0];
    }

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

Complexity

Time: O(N log k) — log k rounds, each merging a total of N nodes.
Space: O(1) — iterative merging relinks existing nodes (a recursive divide-and-conquer would use O(log k) stack).

Complexity Comparison

Approach	Time	Space
Collect and Sort	O(N log N)	O(N)
Merge One by One	O(k · N)	O(1)
Min-Heap	O(N log k)	O(k)
Divide and Conquer	O(N log k)	O(1)

Common Pitfalls

Pushing null heads into the priority queue — the comparator throws a NullPointerException; skip empty lists.
Returning lists[0] without checking k == 0 — an empty array throws ArrayIndexOutOfBoundsException.
Writing the comparator as a.val - b.val is safe here (values are small) but Integer.compare avoids overflow habits in general.
Assuming merge-one-by-one is O(N log k) — the growing result list makes it O(kN).
In divide and conquer, stepping i by interval instead of 2 * interval, which merges the same list twice.