LeetCode 23: Merge k Sorted Lists

Problem Restatement

We are given an array of linked lists:

lists

Each linked list is sorted in ascending order.

We need to merge all linked lists into one sorted linked list and return its head.

The constraints say:

The lists are already individually sorted. (leetcode.com)

Input and Output

Example function shape:

def mergeKLists(lists: list[ListNode]) -> ListNode:
    ...

Examples

Example 1:

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

Merged order:

1,1,2,3,4,4,5,6

Output:

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

Example 2:

lists = []

Output:

[]

Example 3:

lists = [[]]

Output:

[]

First Thought: Merge Lists One by One

We already solved merging two sorted lists in LeetCode 21.

So one natural idea is:

merge list 1 and list 2
merge result with list 3
merge result with list 4
...

Code outline:

result = None

for linked_list in lists:
    result = merge_two_lists(result, linked_list)

This works.

But there is a problem when many lists exist.

Problem With Sequential Merging

Suppose:

k = 100

and each list has similar size.

The merged result keeps growing larger and larger.

Later merges repeatedly traverse many already-merged nodes.

Worst-case complexity becomes:

O(kN)

where:

N = total number of nodes

We need a more balanced approach.

Key Insight

At any moment, we only care about the smallest current node among all list heads.

This is exactly what a min heap does.

The heap always gives the smallest available node in:

O(log k)

time.

Process:

1. Put the first node of every non-empty list into the heap.
2. Extract the smallest node.
3. Add it to the merged list.
4. If that node has a next node, push the next node into the heap.
5. Repeat until the heap becomes empty.

The heap size never exceeds k.

Why the Heap Works

Each list is already sorted.

So:

• when we remove a node from a list
• the next node from that list is the only possible new candidate from that list

The heap stores exactly the smallest remaining node from every active list.

Therefore the heap top is always the globally smallest remaining node.

Visual Walkthrough

Use:

lists = [
  1 -> 4 -> 5,
  1 -> 3 -> 4,
  2 -> 6
]

Initial heap:

1, 1, 2

Pop smallest:

1

Add it to the result.

Push its next node:

4

Heap now:

1, 2, 4

Pop:

1

Push its next:

3

Heap:

2, 3, 4

Continue:

2 -> push 6
3 -> push 4
4 -> push 5
4
5
6

Final merged list:

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Algorithm

1. Create an empty min heap.
2. Push the first node of every non-empty list into the heap.
3. Create a dummy node for the result list.
4. While the heap is not empty:
   • pop the smallest node
   • attach it to the result
   • if the popped node has a next node, push the next node into the heap
5. Return dummy.next.

Handling Heap Comparison in Python

Python heaps compare tuple elements in order.

We store:

(node.val, unique_id, node)

The unique_id prevents comparison errors when two nodes have the same value.

Without it, Python may try to compare ListNode objects directly, which is not supported.

Correctness

The heap always contains the smallest unmerged node from each non-empty list.

The smallest node among all remaining nodes must therefore be at the top of the heap.

Each iteration removes that smallest node and appends it to the result list.

After removing a node from one list, the next node from that list becomes the next candidate and is inserted into the heap.

Since each list is individually sorted, no smaller node from that list can appear later.

Therefore nodes are appended to the result in globally sorted order.

Every node is inserted into and removed from the heap exactly once, so every input node appears exactly once in the merged result.

Thus the algorithm returns one fully merged sorted linked list.

Complexity

Here:

N = total number of nodes
k = number of lists

Implementation

from typing import Optional
import heapq

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def mergeKLists(
        self,
        lists: list[Optional[ListNode]]
    ) -> Optional[ListNode]:
        heap = []

        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i, node))

        dummy = ListNode()
        current = dummy

        while heap:
            _, i, node = heapq.heappop(heap)

            current.next = node
            current = current.next

            if node.next:
                heapq.heappush(
                    heap,
                    (node.next.val, i, node.next)
                )

        return dummy.next

Code Explanation

Create the heap:

heap = []

Push the first node of every non-empty list:

for i, node in enumerate(lists):
    if node:
        heapq.heappush(heap, (node.val, i, node))

The tuple contains:

Create the merged result list:

dummy = ListNode()
current = dummy

Extract the smallest node:

_, i, node = heapq.heappop(heap)

Attach it:

current.next = node
current = current.next

Push the next node from the same list:

if node.next:
    heapq.heappush(
        heap,
        (node.next.val, i, node.next)
    )

Finally:

return dummy.next

Testing

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

def to_list(head):
    result = []

    while head:
        result.append(head.val)
        head = head.next

    return result

def run_tests():
    s = Solution()

    lists = [
        build_list([1, 4, 5]),
        build_list([1, 3, 4]),
        build_list([2, 6]),
    ]

    assert to_list(s.mergeKLists(lists)) == [
        1, 1, 2, 3, 4, 4, 5, 6
    ]

    assert to_list(s.mergeKLists([])) == []

    lists = [build_list([])]
    assert to_list(s.mergeKLists(lists)) == []

    lists = [
        build_list([1]),
        build_list([0]),
    ]

    assert to_list(s.mergeKLists(lists)) == [0, 1]

    lists = [
        build_list([-10, -5, 0]),
        build_list([-6, -2, 3]),
        build_list([1, 2]),
    ]

    assert to_list(s.mergeKLists(lists)) == [
        -10, -6, -5, -2, 0, 1, 2, 3
    ]

    print("all tests passed")

run_tests()