Algorithm

Reorder List

Two Pointer Pattern

Reorder List

Given the head of a singly linked list L0 → L1 → … → Ln-1 → Ln, rearrange the nodes in place so the order becomes L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … — the first node, then the last, then the second, then the second-to-last, and so on, weaving inward from both ends. You rewire the existing nodes (do not create new ones and do not just swap values); the function returns nothing and mutates the list directly.

CONSTRAINTS
  • Number of nodes: 1 to 50,000
  • 1 <= Node.val <= 1000
  • Must be done in place, without allocating a new list
EXAMPLE 1
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Front and back interleave: 1 (first), 4 (last), 2 (second), 3 (second-to-last).
EXAMPLE 2
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
With an odd count the middle node (3) lands last, after all outer pairs have been woven in.
Can this be done in a single forward pass?
No. The target order needs nodes from the back, which a singly linked list cannot reach going forward. You reverse the second half (or use a stack) first — at least two logical passes.
May I move values instead of relinking nodes?
The intended solution rewires the .next pointers in place. Ask, but assume node relinking rather than value copying.
Does the function return the new head?
No — the head node (L0) stays first, and the list is modified in place, so there is nothing to return.

We must weave the list from both ends: first node, last node, second node, second-to-last, and so on. That "front, back, front, back" order is the same both-ends instinct behind every converging problem — but a singly linked list can only move forward, so we cannot just grab nodes from the tail. This is the very obstacle we hit in Palindrome Linked List, and the fix is the same recipe, with a different final step.

The easy escape, and why we avoid it

Dump all the node references into an array, then reconnect them by taking one from the front, one from the back, inward. Simple, but it costs O(N) extra memory for the array — against the in-place requirement.

python
nodes = []
curr = head
while curr:
    nodes.append(curr)
    curr = curr.next
left, right = 0, len(nodes) - 1
while left < right:
    nodes[left].next = nodes[right]
    left += 1
    if left == right:
        break
    nodes[right].next = nodes[left]
    right -= 1
nodes[left].next = None
Split it, flip the back, then zip the two halves

Same first two moves as Palindrome Linked List. Find the middle with fast/slow pointers, cut the list in two, and reverse the second half so its tail becomes a forward-walkable head. Now we hold two strands: the front half in original order, and the back half running from the old tail inward. What's new is the last step — instead of comparing the two halves, we interleave them: take one node from the front, then one from the reversed back, then front, then back, relinking as we go. That alternation is exactly the L0, Ln, L1, Ln-1 pattern.

python
# 1. Find the middle with fast/slow
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next

# 2. Cut, then reverse the second half
second = slow.next
slow.next = None          # sever the two halves
prev = None
while second:
    nxt = second.next
    second.next = prev
    prev = second
    second = nxt

# 3. Weave the front half and the reversed back half together
first, second = head, prev
while second:
    tmp1, tmp2 = first.next, second.next   # remember where each half continues
    first.next = second                    # front node points to a back node
    second.next = tmp1                      # that back node points to the next front node
    first, second = tmp1, tmp2             # advance both halves
Crucial Notecutting the list with slow.next = None is not optional. Skip it and the end of the front half still points into the second half, so after weaving you get a cycle — the list loops forever. Severing first guarantees the two strands are independent before we start relinking them.
Why the halves line up

Fast/slow leaves the front half the same length as the back half, or one node longer when the count is odd. So as we alternate front, back, front, back, the reversed back half runs out first (or at the same time). Looping while second still has nodes weaves in every back node; the front half's leftover node — the middle one, in an odd list — is already linked at the end and simply stays put. No off-by-one special case needed.

Worked example:head = 1 → 2 → 3 → 4
- Find middle: slow lands on 2, so the front half is 1 → 2 and the back half starts at 3.
- Cut and reverse: front half 1 → 2 (2's next set to null); back half 3 → 4 reversed to 4 → 3, head prev = node 4.
- Weave: first=1, second=4. Save 2 and 3. Link 1 → 4, then 4 → 2. Advance to first=2, second=3. Save null, null. Link 2 → 3, then 3 → null. Result: 1 → 4 → 2 → 3.
Where this sits in the family

Palindrome Linked List and Reorder List are the same combo — fast/slow to find the middle, reversal to flip a half — differing only in the payoff: one compares the halves, the other interleaves them. Keep the trio together as a single reusable move for linked lists: find middle → reverse a half → walk the two halves in step. Whenever a list problem wants you to relate the front to the back but the structure only runs forward, this is the shape to reach for. All three phases are O(N) time, and because we only relink existing nodes, O(1) extra space.

Interactive Strategy Visualization
LIST REORDER PROTOCOL

Recursive Folding Strategy

Fragment A
1
2
Fragment B
3
4

Process Step

Phase 1: Binary Fragmentation

We use the Slow & Fast technique to identify the exact midpoint. We then severe the list into two discrete fragments: List A and List B.

Folding Trick

We are essentially folding the list onto itself. Reversing the second half is what enables this symmetrical weave.

Strategy: Three-Stage Metamorphosis

1. Find Mid & Split → 2. Reverse Second Fragment → 3. Interleaved Zipper Merge.

O(N) Time · O(N) Space Array of Nodes
→
O(N) Time · O(1) Space Split, Reverse, Weave