# LeetCode 148: Sort List

## Problem Restatement

We are given the head of a singly linked list.

Return the list after sorting it in ascending order.

The problem asks for an `O(n log n)` time solution. The follow-up asks whether we can sort the list with constant extra space. The number of nodes is in the range `[0, 5 * 10^4]`, and node values are between `-10^5` and `10^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]
```

Example 3:

```python
head = []
```

Output:

```python
[]
```

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[ListNode]` |
| Output | Head of the sorted linked list |
| Sort order | Ascending |
| Target time | `O(n log n)` |
| Follow-up space | `O(1)` extra space |

Function shape:

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

## First Thought: Convert to Array

A simple solution is:

1. Walk through the linked list.
2. Store all node values in an array.
3. Sort the array.
4. Write the sorted values back to the list.

This is easy, but it uses `O(n)` extra space and modifies node values instead of rearranging nodes.

The linked-list-native solution is merge sort.

## Key Insight

Merge sort fits linked lists well.

For arrays, merge sort needs extra space to merge values.

For linked lists, merging can be done by changing `next` pointers.

The idea:

1. Split the list into two halves.
2. Sort each half recursively.
3. Merge the two sorted halves.

This gives `O(n log n)` time because each level processes all nodes once, and there are `O(log n)` levels.

## Finding the Middle

Use slow and fast pointers.

```python
slow = head
fast = head.next
```

Move:

```python
slow = slow.next
fast = fast.next.next
```

When `fast` reaches the end, `slow` points to the node before the start of the second half.

For:

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

the split becomes:

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

Then we disconnect the halves:

```python
second = slow.next
slow.next = None
```

## Merging Two Sorted Lists

After recursively sorting both halves, we merge them.

Example:

```text
left:  2 -> 4
right: 1 -> 3
```

Compare the heads:

```text
1 is smaller than 2
```

Take `1`.

Then compare:

```text
2 and 3
```

Take `2`.

Continue until one list is empty.

Result:

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

## Algorithm

Use recursive merge sort.

For `sortList(head)`:

1. If `head` is `None` or `head.next` is `None`, return `head`.
2. Use slow and fast pointers to find the middle.
3. Split the list into two halves.
4. Recursively sort the left half.
5. Recursively sort the right half.
6. Merge the two sorted halves.
7. Return the merged head.

## Correctness

The base case is correct because an empty list or a one-node list is already sorted.

For a longer list, the algorithm splits it into two smaller linked lists. By the recursive assumption, each half is returned in sorted order.

The merge step repeatedly chooses the smaller head node from the two sorted halves. This keeps the output sorted at every step. Since every node from both halves is appended exactly once, the merged list contains exactly all nodes from the original list.

Therefore, each recursive call returns a sorted version of its input list. Applying this to the original head returns the whole linked list sorted in ascending order.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | Each level merges all nodes, and there are `log n` levels |
| Space | `O(log n)` | Recursive call stack |

The merge itself uses `O(1)` extra pointer space.

Strictly speaking, the recursive version uses `O(log n)` stack space. A bottom-up iterative merge sort can achieve `O(1)` extra space.

## 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 sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        slow = head
        fast = head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        second = slow.next
        slow.next = None

        left = self.sortList(head)
        right = self.sortList(second)

        return self.merge(left, right)

    def merge(
        self,
        left: Optional[ListNode],
        right: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy = ListNode(0)
        tail = dummy

        while left and right:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next

            tail = tail.next

        if left:
            tail.next = left
        else:
            tail.next = right

        return dummy.next
```

## Code Explanation

The base case handles empty and one-node lists:

```python
if head is None or head.next is None:
    return head
```

Then we find the middle:

```python
slow = head
fast = head.next
```

Starting `fast` at `head.next` helps split a two-node list into one node and one node.

The loop moves the pointers:

```python
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
```

Then split:

```python
second = slow.next
slow.next = None
```

Now `head` starts the first half, and `second` starts the second half.

Recursively sort both halves:

```python
left = self.sortList(head)
right = self.sortList(second)
```

Then merge:

```python
return self.merge(left, right)
```

The merge function uses a dummy node:

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

At each step, attach the smaller node:

```python
if left.val <= right.val:
    tail.next = left
    left = left.next
else:
    tail.next = right
    right = right.next
```

When one side is empty, append the rest:

```python
if left:
    tail.next = left
else:
    tail.next = right
```

Return the real merged head:

```python
return dummy.next
```

## Bottom-Up O(1) Space Version

The recursive version is usually accepted and easy to explain.

For the follow-up, we can remove recursion by using bottom-up merge sort.

The idea:

1. Compute the length of the list.
2. Merge sorted blocks of size `1`.
3. Then merge blocks of size `2`.
4. Then size `4`, `8`, and so on.

```python
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head

        n = 0
        curr = head

        while curr:
            n += 1
            curr = curr.next

        dummy = ListNode(0, head)
        size = 1

        while size < n:
            prev = dummy
            curr = dummy.next

            while curr:
                left = curr
                right = self.split(left, size)
                curr = self.split(right, size)

                prev = self.merge_into(left, right, prev)

            size *= 2

        return dummy.next

    def split(
        self,
        head: Optional[ListNode],
        size: int,
    ) -> Optional[ListNode]:
        if head is None:
            return None

        curr = head

        for _ in range(size - 1):
            if curr.next is None:
                break
            curr = curr.next

        next_head = curr.next
        curr.next = None

        return next_head

    def merge_into(
        self,
        left: Optional[ListNode],
        right: Optional[ListNode],
        prev: ListNode,
    ) -> ListNode:
        curr = prev

        while left and right:
            if left.val <= right.val:
                curr.next = left
                left = left.next
            else:
                curr.next = right
                right = right.next

            curr = curr.next

        curr.next = left if left else right

        while curr.next:
            curr = curr.next

        return curr
```

This version has:

| Metric | Value |
|---|---:|
| Time | `O(n log n)` |
| Extra space | `O(1)` |

It is longer, but it satisfies the follow-up more strictly.

## 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.sortList(head)) == [1, 2, 3, 4]

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

    head = build_list([])
    assert to_list(s.sortList(head)) == []

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

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

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

    head = build_list([2, 2, 1, 1])
    assert to_list(s.sortList(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]` | Mixed negative and positive values |
| `[]` | Empty list |
| `[1]` | Single node |
| Already sorted | Should remain sorted |
| Reverse sorted | Harder ordering case |
| Duplicates | Equal values handled correctly |