# LeetCode 143: Reorder List

## Problem Restatement

We are given the head of a singly linked list.

The list can be written as:

```text
L0 -> L1 -> L2 -> ... -> Ln-1 -> Ln
```

We need to reorder it into:

```text
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...
```

The reordering must be done in-place. We may change node links, but we may not modify node values. The function returns nothing. LeetCode states this exact in-place requirement for the problem.

## Examples

Example 1:

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

After reordering:

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

Example 2:

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

After reordering:

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

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head: Optional[ListNode]` |
| Output | Nothing |
| Operation | Modify the linked list in-place |
| Constraint | Node values must not be changed |
| Desired order | First node, last node, second node, second-last node, and so on |

Function shape:

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

## First Thought: Store Nodes in an Array

A simple solution is to store every node in an array.

Then use two pointers:

```text
left = 0
right = n - 1
```

Connect:

```text
nodes[left] -> nodes[right] -> nodes[left + 1] -> nodes[right - 1] ...
```

This is easy, but it uses `O(n)` extra space.

We can do the same reordering with `O(1)` extra space by changing the list structure directly.

## Key Insight

The target order alternates between:

1. the first half in normal order
2. the second half in reverse order

For example:

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

Split into:

```text
first half:  1 -> 2 -> 3
second half: 4 -> 5
```

Reverse the second half:

```text
5 -> 4
```

Then merge alternately:

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

So the algorithm has three phases:

1. Find the middle.
2. Reverse the second half.
3. Merge the two halves alternately.

This is the standard `O(n)` time and `O(1)` space approach.

## Step 1: Find the Middle

Use slow and fast pointers.

```python
slow = head
fast = head
```

Move:

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

When `fast` reaches the end, `slow` is near the middle.

For:

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

`slow` stops at `3`.

For:

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

`slow` stops at `2`.

We will split after `slow`.

## Step 2: Reverse the Second Half

After finding the middle:

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

This splits the list into two lists.

Then reverse `second`.

Example:

```text
4 -> 5
```

becomes:

```text
5 -> 4
```

The standard linked-list reversal uses three pointers:

```python
prev = None
curr = second
```

Then repeatedly redirect:

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

## Step 3: Merge Alternately

Now we have:

```text
first:  1 -> 2 -> 3
second: 5 -> 4
```

Merge one node from `first`, then one node from `second`.

Result:

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

We only need to loop while `second` exists, because the first half is always at least as long as the second half.

## Algorithm

1. If the list has zero or one node, return.
2. Find the middle using slow and fast pointers.
3. Split the list after the middle.
4. Reverse the second half.
5. Merge the first half and reversed second half alternately.

## Correctness

After the middle step, the list is split into two parts. The first part contains the earlier nodes in their original order. The second part contains the later nodes in their original order.

After reversing the second part, its nodes appear from the end of the original list backward:

```text
Ln -> Ln-1 -> Ln-2 -> ...
```

The merge step alternates one node from the first half and one node from the reversed second half.

Therefore, the merged list begins:

```text
L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2
```

which is exactly the required order.

All operations only change `next` pointers. No node value is modified. Therefore, the algorithm produces the required in-place reordered list.

## Complexity

Let `n` be the number of nodes.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | Find middle, reverse half, and merge |
| Space | `O(1)` | Only pointer variables are used |

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

        slow = head
        fast = head

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

        second = slow.next
        slow.next = None

        prev = None
        curr = second

        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        first = head
        second = prev

        while second:
            first_next = first.next
            second_next = second.next

            first.next = second
            second.next = first_next

            first = first_next
            second = second_next
```

## Code Explanation

First, handle very short lists:

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

A list with zero or one node already satisfies the required order.

Find the middle:

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

After this loop, `slow` points to the end of the first half.

Split the list:

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

This line is important. Without it, the final list can accidentally form a cycle.

Reverse the second half:

```python
prev = None
curr = second

while curr:
    next_node = curr.next
    curr.next = prev
    prev = curr
    curr = next_node
```

After reversal, `prev` is the head of the reversed second half.

Then merge:

```python
first = head
second = prev
```

At each step, save the next pointers first:

```python
first_next = first.next
second_next = second.next
```

Then connect:

```python
first.next = second
second.next = first_next
```

Move both pointers forward:

```python
first = first_next
second = second_next
```

The merge stops when the reversed second half is exhausted.

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

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

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

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 4]` | Even-length list |
| `[1, 2, 3, 4, 5]` | Odd-length list |
| `[1]` | Single node |
| `[1, 2]` | Two nodes already stay valid |
| `[1, 2, 3]` | Small odd-length reorder |