# LeetCode 86: Partition List

## Problem Restatement

We are given the head of a linked list and an integer `x`.

We need to reorder the list so that:

```python
nodes with value < x
```

come before:

```python
nodes with value >= x
```

The relative order inside each group must stay the same.

The official statement says to partition the list around `x`, preserving the original relative order of nodes in both partitions. The constraints allow `0` to `200` nodes, node values from `-100` to `100`, and `x` from `-200` to `200`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a linked list and integer `x` |
| Output | Head of the partitioned linked list |
| First group | Nodes with value `< x` |
| Second group | Nodes with value `>= x` |
| Order rule | Preserve original relative order inside each group |

Function shape:

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

## Examples

Example 1:

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

Nodes less than `3` are:

```python
1, 2, 2
```

Nodes greater than or equal to `3` are:

```python
4, 3, 5
```

Preserve the original order in both groups.

Answer:

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

Example 2:

```python
head = [2, 1]
x = 2
```

Nodes less than `2`:

```python
1
```

Nodes greater than or equal to `2`:

```python
2
```

Answer:

```python
[1, 2]
```

## First Thought: Collect Values in Arrays

A simple method is to scan the linked list and put values into two arrays.

```python
small = []
large = []
```

For each node:

```python
if node.val < x:
    small.append(node.val)
else:
    large.append(node.val)
```

Then build a new linked list from:

```python
small + large
```

This preserves order, but it creates new storage for values and new nodes.

We can solve the problem by rearranging the existing nodes directly.

## Key Insight

We need two ordered groups:

1. Nodes with value `< x`
2. Nodes with value `>= x`

A clean way to build them is to maintain two separate linked lists while scanning the original list.

Use two dummy heads:

```python
less_dummy
greater_dummy
```

and two tails:

```python
less_tail
greater_tail
```

When we see a node with value `< x`, append it to the `less` list.

Otherwise, append it to the `greater` list.

At the end, connect:

```python
less_tail.next = greater_dummy.next
```

Then terminate the greater list:

```python
greater_tail.next = None
```

The termination is important. The original nodes still have their old `next` pointers. Without cutting the final pointer, the result can accidentally keep stale links or form an incorrect chain.

## Algorithm

Create two dummy nodes:

```python
less_dummy = ListNode(0)
greater_dummy = ListNode(0)
```

Create two tail pointers:

```python
less_tail = less_dummy
greater_tail = greater_dummy
```

Scan the original list using `cur`.

For each node:

1. Save the next node.
2. If `cur.val < x`, append `cur` to the less list.
3. Otherwise, append `cur` to the greater list.
4. Move to the saved next node.

After the scan:

1. Set `greater_tail.next = None`.
2. Set `less_tail.next = greater_dummy.next`.
3. Return `less_dummy.next`.

## Walkthrough

Use:

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

Start with two empty lists:

```python
less:    dummy
greater: dummy
```

Read `1`.

Since `1 < 3`, append it to `less`:

```python
less:    1
greater:
```

Read `4`.

Since `4 >= 3`, append it to `greater`:

```python
less:    1
greater: 4
```

Read `3`.

Since `3 >= 3`, append it to `greater`:

```python
less:    1
greater: 4 -> 3
```

Read `2`.

Since `2 < 3`, append it to `less`:

```python
less:    1 -> 2
greater: 4 -> 3
```

Read `5`.

Since `5 >= 3`, append it to `greater`:

```python
less:    1 -> 2
greater: 4 -> 3 -> 5
```

Read final `2`.

Since `2 < 3`, append it to `less`:

```python
less:    1 -> 2 -> 2
greater: 4 -> 3 -> 5
```

Connect the two lists:

```python
1 -> 2 -> 2 -> 4 -> 3 -> 5
```

## Correctness

The algorithm scans the original list from left to right.

Whenever it sees a node with value `< x`, it appends that node to the end of the less list. Since nodes are appended in scan order, the less list preserves the original relative order of all nodes with value `< x`.

Whenever it sees a node with value `>= x`, it appends that node to the end of the greater list. Since nodes are appended in scan order, the greater list preserves the original relative order of all nodes with value `>= x`.

Every original node is appended to exactly one of the two lists, because every value either satisfies `val < x` or `val >= x`.

After the scan, connecting the tail of the less list to the head of the greater list places all smaller nodes before all greater-or-equal nodes. Since each partition already preserves its own order, the final list satisfies all requirements.

Therefore, the algorithm returns the correct partitioned list.

## Complexity

Let:

```python
n = number of nodes
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(1)` | Only dummy nodes and pointers are used |

The output reuses the original linked list nodes.

## Implementation

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

class Solution:
    def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
        less_dummy = ListNode(0)
        greater_dummy = ListNode(0)

        less_tail = less_dummy
        greater_tail = greater_dummy

        cur = head

        while cur:
            nxt = cur.next

            if cur.val < x:
                less_tail.next = cur
                less_tail = less_tail.next
            else:
                greater_tail.next = cur
                greater_tail = greater_tail.next

            cur = nxt

        greater_tail.next = None
        less_tail.next = greater_dummy.next

        return less_dummy.next
```

## Code Explanation

Create two dummy heads:

```python
less_dummy = ListNode(0)
greater_dummy = ListNode(0)
```

The dummy nodes simplify appending. We do not need special logic for the first node in either list.

Create tails:

```python
less_tail = less_dummy
greater_tail = greater_dummy
```

Scan the original list:

```python
cur = head
```

Before rewiring a node, save its original next pointer:

```python
nxt = cur.next
```

If the current node belongs in the less partition:

```python
if cur.val < x:
    less_tail.next = cur
    less_tail = less_tail.next
```

Otherwise, append it to the greater partition:

```python
else:
    greater_tail.next = cur
    greater_tail = greater_tail.next
```

Move forward using the saved pointer:

```python
cur = nxt
```

After all nodes are distributed, terminate the greater list:

```python
greater_tail.next = None
```

Then connect the two partitions:

```python
less_tail.next = greater_dummy.next
```

Return the real head:

```python
return less_dummy.next
```

## Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

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

    return values

def check(values, x, expected):
    s = Solution()
    head = build_list(values)
    result = s.partition(head, x)
    assert to_list(result) == expected

def run_tests():
    check([1, 4, 3, 2, 5, 2], 3, [1, 2, 2, 4, 3, 5])
    check([2, 1], 2, [1, 2])
    check([], 3, [])
    check([1], 2, [1])
    check([3], 2, [3])
    check([1, 2, 2], 3, [1, 2, 2])
    check([4, 5, 6], 3, [4, 5, 6])
    check([3, 1, 2, 3, 0], 3, [1, 2, 0, 3, 3])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 4, 3, 2, 5, 2]`, `x = 3` | Main example |
| `[2, 1]`, `x = 2` | Small reorder case |
| `[]` | Empty list |
| Single node less than `x` | One-node less partition |
| Single node greater than or equal to `x` | One-node greater partition |
| All nodes less than `x` | Greater partition empty |
| All nodes greater than or equal to `x` | Less partition empty |
| `[3, 1, 2, 3, 0]` | Preserves order inside both groups |