# LeetCode 23: Merge k Sorted Lists

## Problem Restatement

We are given an array of linked lists:

```text
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:

| Constraint | Value |
|---|---|
| `k == lists.length` | Number of linked lists |
| `0 <= k <= 10^4` | Number of lists |
| `0 <= lists[i].length <= 500` | Length of each list |
| Total nodes across all lists | At most `10^4` |

The lists are already individually sorted. ([leetcode.com](https://leetcode.com/problems/merge-k-sorted-lists/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | An array of sorted linked list heads |
| Output | One merged sorted linked list |
| Order | Ascending |
| Lists may be empty | Yes |
| Node reuse | We can relink existing nodes |

Example function shape:

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

## Examples

Example 1:

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

Merged order:

```text
1,1,2,3,4,4,5,6
```

Output:

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

Example 2:

```text
lists = []
```

Output:

```text
[]
```

Example 3:

```text
lists = [[]]
```

Output:

```text
[]
```

## First Thought: Merge Lists One by One

We already solved merging two sorted lists in LeetCode 21.

So one natural idea is:

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

Code outline:

```python
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:

```text
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:

```text
O(kN)
```

where:

```text
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:

```text
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:

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

Initial heap:

```text
1, 1, 2
```

Pop smallest:

```text
1
```

Add it to the result.

Push its next node:

```text
4
```

Heap now:

```text
1, 2, 4
```

Pop:

```text
1
```

Push its next:

```text
3
```

Heap:

```text
2, 3, 4
```

Continue:

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

Final merged list:

```text
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:

```python
(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

| Metric | Value | Why |
|---|---|---|
| Time | `O(N log k)` | Each of the `N` nodes performs one heap push and one heap pop |
| Space | `O(k)` | The heap stores at most one active node from each list |

Here:

```text
N = total number of nodes
k = number of lists
```

## Implementation

```python
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:

```python
heap = []
```

Push the first node of every non-empty list:

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

The tuple contains:

| Part | Purpose |
|---|---|
| `node.val` | Heap ordering |
| `i` | Tie-breaker for equal values |
| `node` | Actual node reference |

Create the merged result list:

```python
dummy = ListNode()
current = dummy
```

Extract the smallest node:

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

Attach it:

```python
current.next = node
current = current.next
```

Push the next node from the same list:

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

Finally:

```python
return dummy.next
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| Standard example | Multiple sorted lists |
| Empty `lists` | No linked lists |
| `[[]]` | One empty list |
| Single-node lists | Small merge |
| Mixed negative and positive values | General ordering check |