# Reorder List

- **Canonical ID**: `reorder-list`
- **Canonical URL**: https://dsacheatsheet.com/problems/reorder-list
- **Difficulty**: medium
- **Patterns**: Linked Lists
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/reorder-list/

## 1. Core Invariant / The Trick

Three O(1)-space primitives composed in sequence: (1) find middle via fast/slow pointers, (2) split (`slow.next = None`) and reverse the second half, (3) zipper-merge the two halves alternatingly.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Each of the three stages executes one linear traversal modifying only `next` pointers in place.

## 3. Minimal Idiomatic Code

### Python
```python
def reorderList(head: Optional[ListNode]) -> None:
    if not head or not head.next:
        return
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    second = slow.next
    slow.next = None
    prev = None
    while second:
        nxt = second.next
        second.next = prev
        prev = second
        second = nxt
    first, second = head, prev
    while second:
        t1, t2 = first.next, second.next
        first.next = second
        second.next = t1
        first, second = t1, t2
```

### TypeScript
```typescript
export function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;
  let slow: ListNode | null = head;
  let fast: ListNode | null = head.next;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  let second = slow!.next;
  slow!.next = null;
  let prev: ListNode | null = null;
  while (second) {
    const nxt = second.next;
    second.next = prev;
    prev = second;
    second = nxt;
  }
  let first: ListNode | null = head;
  second = prev;
  while (second) {
    const t1 = first!.next;
    const t2 = second.next;
    first!.next = second;
    second.next = t1;
    first = t1;
    second = t2;
  }
}
```

### C++
```cpp
void reorderList(ListNode* head) {
    if (!head || !head->next) return;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode *second = slow->next, *prev = nullptr;
    slow->next = nullptr;
    while (second) {
        ListNode* nxt = second->next;
        second->next = prev; prev = second; second = nxt;
    }
    ListNode *first = head; second = prev;
    while (second) {
        ListNode *t1 = first->next, *t2 = second->next;
        first->next = second; second->next = t1;
        first = t1; second = t2;
    }
}
```

### Java
```java
void reorderList(ListNode head) {
    if (head == null || head.next == null) return;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = slow.next, prev = null;
    slow.next = null;
    while (second != null) {
        ListNode nxt = second.next;
        second.next = prev; prev = second; second = nxt;
    }
    ListNode first = head; second = prev;
    while (second != null) {
        ListNode t1 = first.next, t2 = second.next;
        first.next = second; second.next = t1;
        first = t1; second = t2;
    }
}
```

### Go
```go
func reorderList(head *ListNode) {
    if head == nil || head.next == nil { return }
    slow, fast := head, head.next
    for fast != nil && fast.next != nil { slow = slow.next; fast = fast.next.next }
    second := slow.next
    slow.next = nil
    var prev *ListNode
    for second != nil {
        nxt := second.next; second.next = prev; prev = second; second = nxt
    }
    first, second := head, prev
    for second != nil {
        t1, t2 := first.next, second.next
        first.next = second; second.next = t1
        first, second = t1, t2
    }
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Forgetting `slow.next = None` before reversing leaves a cycle bridging the two halves.
- Stopping zipper condition carelessly drops the last node on odd-length lists.

### Follow-ups
- Palindrome Linked List uses the exact same midpoint + reverse-second-half primitive.