# LeetCode 328: Odd Even Linked List

## Problem Restatement

We are given the `head` of a singly linked list.

We need to reorder the list so that all nodes at odd positions come first, followed by all nodes at even positions.

The position is 1-indexed:

```text
1st node -> odd
2nd node -> even
3rd node -> odd
4th node -> even
```

This is about node positions, not node values.

The relative order inside each group must stay the same.

For example:

```text
Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4
```

The odd-position nodes are:

```text
1, 3, 5
```

The even-position nodes are:

```text
2, 4
```

So the final list is:

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

The problem requires `O(n)` time and `O(1)` extra space. We must rearrange the existing nodes by changing `next` pointers.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head`, the first node of a singly linked list |
| Output | The head of the reordered linked list |
| Required time | `O(n)` |
| Required extra space | `O(1)` |
| Important detail | Odd and even refer to positions, not values |

Function shape:

```python
def oddEvenList(head: Optional[ListNode]) -> Optional[ListNode]:
    ...
```

## Examples

Example 1:

```text
Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 1 -> 3 -> 5 -> 2 -> 4
```

Odd-position nodes:

```text
1 -> 3 -> 5
```

Even-position nodes:

```text
2 -> 4
```

Connect odd list to even list:

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

Example 2:

```text
Input:  2 -> 1 -> 3 -> 5 -> 6 -> 4 -> 7
Output: 2 -> 3 -> 6 -> 7 -> 1 -> 5 -> 4
```

Odd-position nodes:

```text
2 -> 3 -> 6 -> 7
```

Even-position nodes:

```text
1 -> 5 -> 4
```

Final list:

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

## First Thought: Build Two Lists

A simple idea is to traverse the original linked list and place nodes into two separate lists:

1. One list for odd-position nodes.
2. One list for even-position nodes.

Then connect the odd list to the even list.

This idea is correct, but creating new nodes would use extra space. The problem asks for `O(1)` extra space, so we should reuse the original nodes.

We can still use the same idea, but instead of creating new lists, we rewire the `next` pointers in place.

## Key Insight

Keep two chains while walking through the list:

| Pointer | Meaning |
|---|---|
| `odd` | Tail of the odd-position chain |
| `even` | Tail of the even-position chain |
| `even_head` | First node of the even-position chain |

At the start:

```text
1 -> 2 -> 3 -> 4 -> 5
^    ^
odd  even
```

`even_head` points to node `2`, because we need to attach the even chain after the odd chain at the end.

The pointer rewiring works like this:

```text
odd.next = even.next
odd = odd.next
```

This connects the current odd node to the next odd-position node.

Then:

```text
even.next = odd.next
even = even.next
```

This connects the current even node to the next even-position node.

At the end:

```text
odd.next = even_head
```

This places all even-position nodes after all odd-position nodes.

## Algorithm

Handle small lists first.

If the list is empty or has only one node, return it as-is.

Otherwise:

1. Set `odd = head`.
2. Set `even = head.next`.
3. Save `even_head = even`.
4. While `even` and `even.next` both exist:
   1. Link `odd.next` to `even.next`.
   2. Move `odd` forward.
   3. Link `even.next` to `odd.next`.
   4. Move `even` forward.
5. Link the end of the odd chain to `even_head`.
6. Return `head`.

## Walkthrough

Take:

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

Initial state:

```text
odd = 1
even = 2
even_head = 2
```

First loop:

```text
odd.next = even.next
```

This links `1` to `3`.

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

Move `odd` to `3`.

Then:

```text
even.next = odd.next
```

This links `2` to `4`.

Now we have:

```text
odd chain:  1 -> 3 -> 4 -> 5
even chain: 2 -> 4 -> 5
```

Second loop:

Link `3` to `5`.

Link `4` to `None`.

Now:

```text
odd chain:  1 -> 3 -> 5
even chain: 2 -> 4
```

Finally connect:

```text
5.next = 2
```

Final result:

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

## Correctness

The algorithm maintains two chains.

The odd chain contains the nodes at positions `1, 3, 5, ...` that have already been processed.

The even chain contains the nodes at positions `2, 4, 6, ...` that have already been processed.

At each loop step, `even.next` is the next odd-position node. Assigning:

```python
odd.next = even.next
```

adds that node to the odd chain.

Then `odd.next` is the next even-position node. Assigning:

```python
even.next = odd.next
```

adds that node to the even chain.

The order inside each chain stays unchanged because we always append the next odd node to the odd chain and the next even node to the even chain.

When the loop ends, all nodes have been assigned to exactly one of the two chains. Connecting:

```python
odd.next = even_head
```

places the complete even chain after the complete odd chain.

Therefore, the returned list has all odd-position nodes first, then all even-position nodes, while preserving relative order inside both groups.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited or rewired a constant number of times |
| 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

from typing import Optional

class Solution:
    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None:
            return None

        odd = head
        even = head.next
        even_head = even

        while even is not None and even.next is not None:
            odd.next = even.next
            odd = odd.next

            even.next = odd.next
            even = even.next

        odd.next = even_head

        return head
```

## Code Explanation

Start with the first odd-position node:

```python
odd = head
```

Start with the first even-position node:

```python
even = head.next
```

Save the first even node:

```python
even_head = even
```

We need this later because after the odd chain is complete, we attach the even chain to its end.

The loop condition is:

```python
while even is not None and even.next is not None:
```

This means there is still another odd-position node after the current even node.

Move the next odd node into the odd chain:

```python
odd.next = even.next
odd = odd.next
```

Move the next even node into the even chain:

```python
even.next = odd.next
even = even.next
```

After the loop, connect the two chains:

```python
odd.next = even_head
```

Finally, return the original head:

```python
return head
```

The head stays the same because the first node remains the first node in the reordered list.

## Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

    while head is not None:
        values.append(head.val)
        head = head.next

    return values

def run_tests():
    s = Solution()

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

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

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

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

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

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

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 5]` | Odd number of nodes |
| `[2, 1, 3, 5, 6, 4, 7]` | Longer example |
| `[]` | Empty list |
| `[1]` | Single node |
| `[1, 2]` | Two nodes, already unchanged |
| `[1, 2, 3]` | Small odd-length list |