# LeetCode 147: Insertion Sort List

## Problem Restatement

We are given the head of a singly linked list.

Sort the list using insertion sort and return the new head.

Insertion sort builds a sorted output list one node at a time. At each step, it removes one node from the input, finds where it belongs in the sorted part, and inserts it there. LeetCode gives examples such as `[4,2,1,3] -> [1,2,3,4]` and `[-1,5,3,4,0] -> [-1,0,3,4,5]`.

## Examples

Example 1:

```python
head = [4, 2, 1, 3]
```

Output:

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

Example 2:

```python
head = [-1, 5, 3, 4, 0]
```

Output:

```python
[-1, 0, 3, 4, 5]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[ListNode]` |
| Output | Head of the sorted linked list |
| Sort order | Ascending |
| Algorithm | Insertion sort |
| Node count | From `1` to `5000` |
| Node values | From `-5000` to `5000` |

Function shape:

```python
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        ...
```

## First Thought: Convert to Array

A simple way is:

1. Read all values into an array.
2. Sort the array.
3. Write the sorted values back into the list.

But this does not really implement insertion sort on the linked list. It also modifies values instead of rearranging nodes.

The point of this problem is pointer manipulation.

We should sort by moving nodes.

## Key Insight

Maintain a separate sorted linked list.

Process the original list one node at a time.

For each node:

1. Save its next pointer.
2. Find its correct position in the sorted list.
3. Insert it there.
4. Continue with the saved next node.

A dummy node makes insertion at the front easy.

```text
dummy -> sorted nodes
```

The final sorted head is:

```python
dummy.next
```

## Insertion Example

Input:

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

Start with an empty sorted list:

```text
dummy
```

Insert `4`:

```text
dummy -> 4
```

Insert `2` before `4`:

```text
dummy -> 2 -> 4
```

Insert `1` before `2`:

```text
dummy -> 1 -> 2 -> 4
```

Insert `3` between `2` and `4`:

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

Return `dummy.next`.

## Algorithm

Create a dummy node for the sorted list.

Set `curr = head`.

While `curr` exists:

1. Save the next unsorted node:

```python
next_node = curr.next
```

2. Find the insertion position in the sorted list:

```python
prev = dummy
while prev.next and prev.next.val < curr.val:
    prev = prev.next
```

3. Insert `curr` after `prev`:

```python
curr.next = prev.next
prev.next = curr
```

4. Move to the saved next node:

```python
curr = next_node
```

Return:

```python
dummy.next
```

## Correctness

The algorithm maintains this invariant:

Before each iteration, the list starting at `dummy.next` is sorted and contains exactly the nodes already processed from the original list.

Initially, no nodes have been processed, so the sorted list is empty and the invariant holds.

During each iteration, the algorithm takes one unprocessed node `curr`. It scans the sorted list until it finds the first node with value greater than or equal to `curr.val`. Inserting `curr` before that node keeps the sorted order. All previously processed nodes remain in the list, and `curr` is added exactly once.

Therefore, after the iteration, the sorted list contains exactly all processed nodes and remains sorted.

When the loop finishes, every original node has been processed. By the invariant, `dummy.next` points to a sorted list containing all original nodes.

Thus, the algorithm returns the sorted linked list.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n^2)` | Each insertion may scan the sorted list |
| Space | `O(1)` | Only pointer variables are used |

Insertion sort is quadratic in the worst case, which matches the intended algorithm for this problem.

## Implementation

```python
from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def insertionSortList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = head

        while curr:
            next_node = curr.next

            prev = dummy

            while prev.next and prev.next.val < curr.val:
                prev = prev.next

            curr.next = prev.next
            prev.next = curr

            curr = next_node

        return dummy.next
```

## Code Explanation

The dummy node anchors the sorted list:

```python
dummy = ListNode(0)
```

The current pointer walks through the original list:

```python
curr = head
```

Before moving `curr`, we save the next original node:

```python
next_node = curr.next
```

This is important because insertion changes `curr.next`.

To find the insertion point, start from the dummy node:

```python
prev = dummy
```

Move forward while the next sorted node is smaller:

```python
while prev.next and prev.next.val < curr.val:
    prev = prev.next
```

Insert `curr` after `prev`:

```python
curr.next = prev.next
prev.next = curr
```

Then continue with the saved node:

```python
curr = next_node
```

Finally:

```python
return dummy.next
```

returns the real head of the sorted list.

## Small Optimization

If the input is nearly sorted, we can remember the previous insertion position.

When the next value is larger than the last inserted value, the search can continue from there instead of restarting from the dummy node.

A concise optimized version:

```python
class Solution:
    def insertionSortList(
        self,
        head: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        prev = dummy
        curr = head

        while curr:
            next_node = curr.next

            if prev.val >= curr.val:
                prev = dummy

            while prev.next and prev.next.val < curr.val:
                prev = prev.next

            curr.next = prev.next
            prev.next = curr
            curr = next_node

        return dummy.next
```

The simpler version is easier to reason about. The optimized version still has worst-case `O(n^2)` time.

## Testing

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

def build_list(values):
    dummy = ListNode(0)
    curr = dummy

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

    return dummy.next

def to_list(head):
    result = []
    curr = head

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

    return result

def run_tests():
    s = Solution()

    head = build_list([4, 2, 1, 3])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([-1, 5, 3, 4, 0])
    assert to_list(s.insertionSortList(head)) == [-1, 0, 3, 4, 5]

    head = build_list([1])
    assert to_list(s.insertionSortList(head)) == [1]

    head = build_list([1, 2, 3, 4])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([4, 3, 2, 1])
    assert to_list(s.insertionSortList(head)) == [1, 2, 3, 4]

    head = build_list([2, 2, 1, 1])
    assert to_list(s.insertionSortList(head)) == [1, 1, 2, 2]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[4, 2, 1, 3]` | Standard example |
| `[-1, 5, 3, 4, 0]` | Negative and positive values |
| `[1]` | Single node |
| Already sorted | No major reordering |
| Reverse sorted | Worst-case insertion pattern |
| Duplicates | Equal values remain sorted |