Merge k Sorted Lists

Problem in Plain English

You are given an array of k linked lists that are each sorted in ascending order. Merge them into one sorted linked list and return its head.

Problem Statement

You are given an array lists of k linked lists, where each list is sorted in ascending order and any entry may be empty.

Merge all the lists into one sorted linked list and return its head, reusing the existing nodes where possible. The total number of nodes across all lists is bounded, while k alone can be large.

Lists are terminating, independently owned chains. The rebuilding baseline creates fresh nodes and preserves every input. The pairwise approach splices original nodes and updates the lists array, so callers must allow those mutations.

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 all lists[i].length does not exceed 10^4.

Examples

Example 1

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

The three sorted chains weave into 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Example 2

Input: lists = []
Output: []

No lists means the merged result is empty.

Example 3

Input: lists = [[]]
Output: []

One empty list still merges to an empty result.

Example 4

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

Skip the empty chains, interleave the negative heads in ascending order, and retain all three occurrences of -1. Equal values belong to separate nodes and must not be deduplicated.

Intuition

The smallest remaining value of any sorted chain is at its head. Merging two chains repeatedly takes the smaller head, then attaches an already sorted remainder when one side ends. In Example 1, merging [1,4,5] with [1,3,4] gives [1,1,3,4,4,5]; merging that result with [2,6] gives the answer. Pair lists in balanced rounds so a node participates in at most logarithmically many merges, instead of being rescanned after every newly added list. Empty array entries still cost work to inspect, even when there are few or no nodes.

Approaches

Collect Sort Rebuild

Solution Details

Reveal Collect Sort Rebuild: intuition, complexity, and code

Intuition

Collect all values, apply a numeric comparison sort, and append fresh nodes in that order. This ignores the useful order inside each input but provides a simple baseline that leaves the original node identities and next links untouched. It needs storage for both the value pool and the rebuilt result.

Step-by-Step Logic

Start an empty pool and inspect every entry of lists, including null heads. Follow next in each nonempty chain and append each value. Example 1 appends 1,4,5, then 1,3,4, then 2,6.
Sort the entire pool numerically in ascending order. Example 1 changes [1,4,5,1,3,4,2,6] to [1,1,2,3,4,4,5,6].
Create a dummy and a tail pointer. For each sorted value, allocate a fresh ListNode, attach it after tail and advance tail. Example 1 appends all eight values, including both 1s and both 4s.
Return dummy.next, which is null if no values were collected. Example 1 returns [1,1,2,3,4,4,5,6] while all three original lists remain unchanged.

Why It Works

Every original node is reached once by traversing its own terminating list, so the pool contains exactly the multiset of input values, including all duplicates. A numeric ascending sort only permutes that pool. Appending one new node per sorted entry therefore creates a sorted chain with precisely the required multiplicities. The dummy node is excluded by returning dummy.next. No original node is assigned or linked into the result, so all input chains and the caller's head array remain unchanged.

Dry Run

Collect Sort Rebuild: variable states at each step
action	input pointer before → after	pool / output
initialize	first head A0(1)	pool=[]
read A0	A0(1) → A1(4)	[1]
read A1	A1(4) → A2(5)	[1,4]
read A2	A2(5) → null	[1,4,5]
read B0	B0(1) → B1(3)	[1,4,5,1]
read B1	B1(3) → B2(4)	[1,4,5,1,3]
read B2	B2(4) → null	[1,4,5,1,3,4]
read C0	C0(2) → C1(6)	[1,4,5,1,3,4,2]
read C1	C1(6) → null	[1,4,5,1,3,4,2,6]
library numeric sort	all inputs exhausted	[1,1,2,3,4,4,5,6]
initialize result	tail=dummy	[]
append 1	tail dummy → R0	[1]
append 1	tail R0 → R1	[1,1]
append 2	tail R1 → R2	[1,1,2]
append 3	tail R2 → R3	[1,1,2,3]
append 4	tail R3 → R4	[1,1,2,3,4]
append 4	tail R4 → R5	[1,1,2,3,4,4]
append 5	tail R5 → R6	[1,1,2,3,4,4,5]
append 6	tail R6 → R7	[1,1,2,3,4,4,5,6]
return	dummy.next=R0; R7.next=null	[1,1,2,3,4,4,5,6]; all result identities fresh

Complexity Analysis

Time Complexity

O(k + N\log(N+1))

Space Complexity

O(N)

N is the total node count and k is the number of array entries. Inspecting k heads and collecting N values costs O(k + N); a comparison sort costs O(N log(N+1)), and allocating N result nodes costs O(N). The pool, possible sort workspace and fresh output take O(N) space; the original heads and next links are unchanged. The displayed time assumes the runtime uses an O(N log N) comparison sort, as standard Java and Python implementations do. ECMAScript does not specify Array.sort time or space complexity, so the JavaScript bound is conditional on its engine's sort implementation; the pool and returned nodes alone already need O(N).

Code

Solution.java

1import java.util.List;2import java.util.ArrayList;3import java.util.Collections;4
5// Omit this definition when the platform supplies ListNode.6class ListNode {7    int val;8    ListNode next;9    ListNode(int val) { this.val = val; }10}11
12class Solution {13    public ListNode mergeKLists(ListNode[] lists) {14        List<Integer> vals = new ArrayList<>();15        for (ListNode node : lists) {16            while (node != null) {17                vals.add(node.val);18                node = node.next;19            }20        }21        Collections.sort(vals);22        ListNode dummy = new ListNode(0);23        ListNode tail = dummy;24        for (int val : vals) {25            tail.next = new ListNode(val);26            tail = tail.next;27        }28        return dummy.next;29    }30}

Hints

Hint 1

Pooling every value and sorting works but discards the per-list order, so keep it only as the baseline.

Hint 2

A two-list merge helper that splices nodes with a dummy head is the building block for every better plan.

Hint 3

Merge pairs in rounds with a doubling interval so k chains collapse in logarithmic rounds instead of one-by-one.

Edge Cases

An empty array of lists returns null without entering any merge round.
Entries that are empty lists are skipped naturally by the two-list helper.
One long list plus many empty ones carries the long list through untouched.
Duplicate and negative values retain every node and sort numerically; equal heads choose the right chain without deleting the left node.
An odd number of chains leaves one block unpaired in a round; interval doubling later brings it into slot 0.
At k=10000 with all heads null, merging still costs O(k); with one nonempty list, avoid assuming there are no head-array costs.

Common Mistakes and Interview Tips

Merging lists one after another into a growing accumulator, which repeats work and times out on large k.
Forgetting the empty-input guard and indexing lists[0] when no list exists.
Building fresh nodes in the helper instead of splicing, which wastes the reuse the optimal plan allows.
Using JavaScript's default lexicographic sort, which puts 10 before 2; the rebuilding code supplies a numeric comparator.
Claiming constant space while allocating a new Python array each round; the shown Python code updates the caller's array in place.
Expecting original chains to remain intact after splicing; use rebuilding or clone inputs if callers need preservation.
Passing chains that share nodes into the splicing helper can attach a node to itself; independent chain ownership is required.

Key Takeaway

When many sorted chains must become one, merge pairs in halving rounds so linear two-way merges stack into logarithmic depth.