0
slow
Reorder a linked list from L0 → L1 → … → Ln to L0 → Ln → L1 → Ln-1 → … in-place by combining three classic linked-list primitives: find the middle with slow/fast pointers, reverse the second half, then merge the two halves alternately.
Given a singly-linked list, reorder it in-place so the first node is followed by the last, then the second, then the second-to-last, and so on — without allocating a new list. For 1 → 2 → 3 → 4 → 5 the answer is 1 → 5 → 2 → 4 → 3. For 1 → 2 → 3 → 4 it is 1 → 4 → 2 → 3.
slow at one step and fast at two steps. When fast can't take two more steps, slow sits at the last node of the first half. This is the standard Floyd midpoint.slow.next = null, then reverse the tail with a three-pointer walk (prev, curr, next).p1 (original head) and p2 (reversed head), weaving them together one node at a time. Stop when either pointer runs out (the lengths differ by at most 1).fast.next && fast.next.next (not fast && fast.next). Using the wrong condition shifts slow one node too far, putting the cut in the wrong place for odd-length lists.The array approach is the first thing most people code, and it does work. But interviewers specifically choose this problem to test whether you can do it without a buffer. The three-phase pointer solution uses exactly O(1) extra space and three O(n) passes.
slow moves 1 step, fast moves 2.class ListNode {
val: number;
next: ListNode | null;
constructor(val: number, next: ListNode | null = null) {
this.val = val;
this.next = next;
}
}
function reorderList(head: ListNode | null): void {
if (!head || !head.next) return;
// ── Phase 1: find the middle ──────────────────────────────────────────────
let slow: ListNode = head;
let fast: ListNode | null = head;
while (fast.next && fast.next.next) {
slow = slow.next!;
fast = fast.next.next;
}
// slow is now the last node of the first half
// ── Phase 2: reverse the second half ─────────────────────────────────────
let prev: ListNode | null = null;
let curr: ListNode | null = slow.next;
slow.next = null; // cut the list in two
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
// prev is now the head of the reversed second half
// ── Phase 3: merge alternately ────────────────────────────────────────────
let p1: ListNode | null = head;
let p2: ListNode | null = prev;
while (p1 && p2) {
const n1 = p1.next;
const n2 = p2.next;
p1.next = p2;
p2.next = n1;
p1 = n1;
p2 = n2;
}
}slow advances one step and fast advances two. When the loop ends, slow lands on the last node of the first half. The loop condition fast.next && fast.next.next is the critical detail — it leavesslow at the correct cut point for both even- and odd-length lists.slow.next = null to physically split the list, then walk curr forward while threading each node back to prev. After the loop, prev is the new head of the reversed tail.p1 → p2 → n1, then advances both. Because the second half is at most as long as the first, the loop ends cleanly when either pointer is exhausted.fast.next && fast.next.next is immediately false, so slow stays at head; the second-half list is just the second node reversed, and the merge produces 1 → 2 (already correct).length / 2 steps to find the midpoint — same asymptotic cost, slightly simpler code.prev pointers during the merge phase; the split and reverse are simpler since you already have back-references.| "reorder / interleave first and last" | split + reverse + merge |
| find midpoint of a linked list | slow/fast (Floyd) pointers |
| reverse a linked list in-place | prev/curr/next three-pointer walk |
| "palindrome linked list" check | find mid + reverse second half + compare |
// Phase 1: find middle
let slow = head, fast = head;
while (fast?.next?.next) { slow = slow.next!; fast = fast.next.next; }
// Phase 2: reverse second half
let prev: ListNode | null = null, curr = slow.next;
slow.next = null;
while (curr) { const nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; }
// Phase 3: merge alternately
let p1: ListNode | null = head, p2 = prev;
while (p1 && p2) {
const n1 = p1.next, n2 = p2.next;
p1.next = p2; p2.next = n1;
p1 = n1; p2 = n2;
}1 → 2 → 3 → 4, what is the reordered output?1→2→3→4→5 is: