23. Merge k Sorted Lists

HardLinked Lists and Pointer ManipulationMin-heap (priority queue)K-way merge via min-heap

Merge k Sorted Lists

Given an array of k sorted linked lists, merge all of them into a single sorted linked list and return its head.

In plain English

Produce one globally sorted list from k independently sorted lists as efficiently as possible.

Picture it like this

Like a tournament where each list sends its current smallest contender; the heap referees pick the overall smallest each round and that list sends its next contender.

Example

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Why: Merging the three sorted lists produces one sorted sequence 1,1,2,3,4,4,5,6.

Constraints

k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] is sorted in ascending orderThe sum of lists[i].length does not exceed 10^4

Pattern lesson

See the pattern, then code

K-way merge via min-heap

↗

Linked Lists and Pointer Manipulation

Reversal, cycle detection, merging, reordering, or O(1)-space sequence edits.. The next node of the answer is the smallest among the current heads of all k lists; a heap gives that minimum in O(log k) and lets you push the successor cheaply.

New words, made simpleKnow these before the algorithm

Min-heap: A tree structure that returns and removes the smallest element in O(log size).
Tie-breaker index: The list index stored alongside the value so equal values never force Python to compare ListNode objects.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Concatenate then sort

Discards the sortedness of each list and is slower than exploiting k << N.

Collect all N values, sort them, and rebuild a list.

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

Merge one by one

Simple but early lists get re-scanned k times, quadratic in k.

Fold the lists together with repeated two-list merges.

Time O(N k)Space O(1)

Best choiceMin-heap of heads

Each of the N nodes is pushed and popped once at O(log k), the best general approach.

Keep the current head of each list in a heap and repeatedly extract the minimum.

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

The rule we keep true

Invariant

The heap contains exactly one node per still-active list, namely that list's smallest unconsumed value, so its top is the global minimum of all remaining nodes.

Why this is correct

Reasoning

Every node enters and leaves the heap exactly once; because each list is sorted, pushing a popped node's successor maintains one frontier node per list, guaranteeing the popped sequence is globally non-decreasing.

The algorithm in three movesSay these aloud before coding

1Push the head of every non-empty list into a min-heap keyed by value

heap heads: 1,1,2

2Pop the smallest node and append it to the result tail

pop 1(list0) -> push 4

3If the popped node has a next, push that next into the heap

pop 1(list1) -> push 3

4Repeat until the heap is empty

5Return dummy.next

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Readheads 1,1,2

2 · AskWhat is in the heap?

3 · Update state(1,0),(1,1),(2,2)

4 · ResultReady to extract minima.

Key takeaway

The heap always holds one frontier node per list; the minimum is popped into the merged output.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 6-9Seed the heap
Push the head of every non-empty list; the (val, i, node) tuple keeps ordering by value with i as a safe tie-breaker.
2
Lines 10-11Result scaffold
Dummy plus tail lets us append popped nodes in O(1).
3
Lines 12-17Extract-and-refill loop
Pop the minimum, attach it, and push its successor so each list keeps exactly one node in the heap.
4
Lines 18Return
dummy.next is the fully merged head.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

lists is empty (return None)
Some sublists are empty or None
All lists empty
A single list only

Common beginner mistakes

Pushing bare nodes without a tie-breaker causes 'ListNode not comparable' errors when values are equal
Forgetting to skip empty/None lists when seeding
Reusing tail incorrectly so the final node still points into the middle of the list (set tail = node, and the last node's next is naturally terminated because it had no successor pushed)

Check your understanding

Why is the heap size bounded by k rather than N?

PyPython 3 · solution.py

Optimal

1import heapq23class Solution:4    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:5        heap = []6        for i, node in enumerate(lists):7            if node:8                heapq.heappush(heap, (node.val, i, node))9        dummy = ListNode(0)10        tail = dummy11        while heap:12            val, i, node = heapq.heappop(heap)13            tail.next = node14            tail = node15            if node.next:16                heapq.heappush(heap, (node.next.val, i, node.next))17        return dummy.next

Time complexityO(N log k)Optimized

Space complexityO(k)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMetaMicrosoft

Merge k Sorted Lists

Merge k Sorted Lists

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Linked Lists and Pointer Manipulation