Reorder List

The problem

Reorder a singly linked list in-place to: L0 → Ln → L1 → Ln-1 → L2 → …

Input:  1→2→3→4
Output: 1→4→2→3

Input:  1→2→3→4→5
Output: 1→5→2→4→3

Do not change node values — rewire pointers. Prefer O(1) extra space.

Brute force

Copy nodes to array; rebuild with two indices. O(n) space — say it, then do the three-step in-place.

function reorderListArray(head: ListNode | null): void {
  if (!head) return;
  const nodes: ListNode[] = [];
  let cur: ListNode | null = head;
  while (cur) {
    nodes.push(cur);
    cur = cur.next;
  }
  let i = 0, j = nodes.length - 1;
  while (i < j) {
    nodes[i].next = nodes[j];
    i++;
    if (i === j) break;
    nodes[j].next = nodes[i];
    j--;
  }
  nodes[i].next = null;
}

Optimal: mid + reverse + merge

1. Middle — slow/fast; split into two halves.
2. Reverse second half.
3. Interleave first and reversed second.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function reorderList(head: ListNode | null): void {
  if (!head || !head.next) return;

  // 1) find mid
  let slow: ListNode | null = head;
  let fast: ListNode | null = head;
  while (fast.next && fast.next.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }

  // 2) reverse second half
  let prev: ListNode | null = null;
  let curr: ListNode | null = slow!.next;
  slow!.next = null; // cut
  while (curr) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }

  // 3) merge
  let a: ListNode | null = head;
  let b: ListNode | null = prev;
  while (b) {
    const aNext = a!.next;
    const bNext = b.next;
    a!.next = b;
    b.next = aNext;
    a = aNext;
    b = bNext;
  }
}

Time	O(n)
Space	O(1)

Edge cases

• 0/1/2 nodes
• Odd length — middle stays in first half after cut
• Even length

Common bugs

• Not cutting the list → cycle
• Wrong mid for odd/even
• Losing next pointers while merging
• Off-by-one so last link cycles

Interview delivery

1. Three phases out loud.
2. Reuse reverse-list skill.
3. Dry-run 1..5.
4. O(n)/O(1).
5. Array rebuild if they allow O(n) space first.

Related

• Reverse Linked List
• Middle / remove nth
• Palindrome Linked List patterns
• Merge Two Sorted Lists

Why cut the list

After finding mid, slow.next = null separates halves. If you forget, reverse + merge can create cycles or shared tails that corrupt the structure.

Odd length example 1→2→3→4→5

Mid ends at 3; second half 4→5 reverses to 5→4; merge → 1→5→2→4→3.

Interview narrative

“I’ll reuse three patterns I already know: middle of list, reverse list, merge alternating.” That framing shows composition, not memorization of one monster function.

Further reading

• LeetCode 143 — Reorder List
• MDN: class