# LeetCode 21: Merge Two Sorted Lists

## Problem Restatement

We are given the heads of two sorted linked lists:

```text
list1
list2
```

Both lists are sorted in non-decreasing order.

We need to merge them into one sorted linked list and return the head of the merged list.

The merged list should be made by splicing together the nodes of the original two lists. The constraints say the total number of nodes across both lists is in the range `[0, 50]`, node values are between `-100` and `100`, and both input lists are sorted in non-decreasing order.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Two linked list heads, `list1` and `list2` |
| Output | Head of the merged sorted linked list |
| Sort order | Non-decreasing |
| Empty lists | Either list may be empty |
| Node rule | Reuse nodes by changing pointers |

Example function shape:

```python
def mergeTwoLists(list1: ListNode, list2: ListNode) -> ListNode:
    ...
```

## Examples

Example 1:

```text
list1 = [1, 2, 4]
list2 = [1, 3, 4]
```

Merged result:

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

Example 2:

```text
list1 = []
list2 = []
```

Merged result:

```text
[]
```

Example 3:

```text
list1 = []
list2 = [0]
```

Merged result:

```text
[0]
```

## First Thought: Copy Values Into an Array

A simple approach is:

1. Traverse both lists.
2. Put all values into an array.
3. Sort the array.
4. Build a new linked list from the sorted values.

This works, but it ignores the fact that the two input lists are already sorted.

It also creates new nodes instead of splicing the existing lists together.

```python
class Solution:
    def mergeTwoLists(self, list1, list2):
        values = []

        while list1:
            values.append(list1.val)
            list1 = list1.next

        while list2:
            values.append(list2.val)
            list2 = list2.next

        values.sort()

        dummy = ListNode()
        current = dummy

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

        return dummy.next
```

## Problem With This Approach

This solution does extra work.

| Metric | Value |
|---|---|
| Time | `O((m + n) log(m + n))` |
| Space | `O(m + n)` |

The lists are already sorted, so we can merge them in linear time.

## Key Insight

This is the linked-list version of the merge step from merge sort.

At each step, compare the current heads of both lists.

Choose the smaller node and attach it to the result.

Then move forward in the list that supplied that node.

For example:

```text
list1: 1 -> 2 -> 4
list2: 1 -> 3 -> 4
```

Compare the first nodes:

```text
1 and 1
```

Choose one `1`.

Then compare:

```text
2 and 1
```

Choose `1`.

Continue until one list is empty.

At that point, attach the rest of the other list directly.

## Why a Dummy Node Helps

A dummy node gives us a stable starting point for the result list.

Without a dummy node, we need special logic for the first node.

With a dummy node:

```text
dummy -> merged nodes
```

we always attach to:

```python
current.next
```

At the end, return:

```python
dummy.next
```

which skips the fake starting node.

## Visual Walkthrough

Use:

```text
list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4
```

Start:

```text
dummy
current = dummy
```

Compare `1` and `1`.

Attach `list1` node:

```text
dummy -> 1
list1 now points to 2 -> 4
```

Compare `2` and `1`.

Attach `list2` node:

```text
dummy -> 1 -> 1
list2 now points to 3 -> 4
```

Compare `2` and `3`.

Attach `2`:

```text
dummy -> 1 -> 1 -> 2
list1 now points to 4
```

Compare `4` and `3`.

Attach `3`:

```text
dummy -> 1 -> 1 -> 2 -> 3
list2 now points to 4
```

Compare `4` and `4`.

Attach one `4`.

Then one list becomes empty, so attach the remaining list.

Final result:

```text
1 -> 1 -> 2 -> 3 -> 4 -> 4
```

## Algorithm

1. Create a dummy node.
2. Set `current = dummy`.
3. While both `list1` and `list2` are not empty:
   - compare `list1.val` and `list2.val`
   - attach the smaller node to `current.next`
   - move the chosen list forward
   - move `current` forward
4. Attach whichever list remains.
5. Return `dummy.next`.

## Correctness

The algorithm maintains this invariant:

```text
The list from dummy.next to current is sorted and contains the smallest nodes already chosen from list1 and list2.
```

At each step, the smallest remaining node must be one of the two current heads, because both input lists are sorted.

The algorithm compares those two heads and attaches the smaller one.

So the merged prefix remains sorted, and no smaller unchosen node is skipped.

When one list becomes empty, every remaining node in the other list is already sorted and greater than or equal to the merged prefix tail. Attaching the rest preserves sorted order.

Therefore the algorithm returns a sorted linked list containing all nodes from both input lists.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Each node is visited and attached once |
| Space | `O(1)` | Only pointer variables are used |

Here:

```text
m = length of list1
n = length of list2
```

## Implementation

```python
from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def mergeTwoLists(
        self,
        list1: Optional[ListNode],
        list2: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy

        while list1 and list2:
            if list1.val <= list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next

            current = current.next

        if list1:
            current.next = list1
        else:
            current.next = list2

        return dummy.next
```

## Code Explanation

Create the dummy node:

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

`current` always points to the last node in the merged list.

Loop while both lists still have nodes:

```python
while list1 and list2:
```

Choose the smaller current node:

```python
if list1.val <= list2.val:
    current.next = list1
    list1 = list1.next
else:
    current.next = list2
    list2 = list2.next
```

Move the result pointer forward:

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

After the loop, at least one list is empty.

Attach the remaining list:

```python
if list1:
    current.next = list1
else:
    current.next = list2
```

Return the real head:

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

    list1 = build_list([1, 2, 4])
    list2 = build_list([1, 3, 4])
    assert to_list(s.mergeTwoLists(list1, list2)) == [1, 1, 2, 3, 4, 4]

    list1 = build_list([])
    list2 = build_list([])
    assert to_list(s.mergeTwoLists(list1, list2)) == []

    list1 = build_list([])
    list2 = build_list([0])
    assert to_list(s.mergeTwoLists(list1, list2)) == [0]

    list1 = build_list([-10, -3, 5])
    list2 = build_list([-4, 0, 6])
    assert to_list(s.mergeTwoLists(list1, list2)) == [-10, -4, -3, 0, 5, 6]

    list1 = build_list([1, 1, 1])
    list2 = build_list([1, 1])
    assert to_list(s.mergeTwoLists(list1, list2)) == [1, 1, 1, 1, 1]

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1, 2, 4]`, `[1, 3, 4]` | Standard example |
| `[]`, `[]` | Both lists empty |
| `[]`, `[0]` | One list empty |
| Negative and positive values | Checks ordering across signs |
| Repeated values | Confirms duplicates are preserved |