Reorder List

mediumTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(1)

Linked Lists Original Statement (leetcode).md

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

Each of the three stages executes one linear traversal modifying only `next` pointers in place.

3. Minimal Idiomatic Code

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

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.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Reverse Linked List (O(N))Linked List Cycle (O(N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.