DAY 16 / 30 · WEEK 3

Linked Lists II — Fast/Slow & Reverse

Goal of the day

• Reverse a singly linked list in place using three pointers (prev, cur, next) — no extra list, no recursion needed.
• Use fast/slow pointers (one step at a time, one two steps at a time) to find the middle of a list in a single pass — and see why the same trick detects a cycle.
• Combine both techniques in Reorder List, today's capstone problem.

Concept

Think of a group of people standing in a line holding hands, each one told "point your free hand at whoever is in front of you." To reverse the line, everyone has to let go of the person in front and instead grab the person behind them — one at a time, because if two people let go and re-grab in the wrong order, the chain splits and part of the line is lost forever. That's exactly Day 15's "capture before you overwrite" lesson, applied to every node instead of just one.

Reversal. Walk the list once, and at each node, flip its .next to point backward instead of forward. Three pointers make this safe: prev (the reversed portion built so far), cur (the node being flipped right now), and a temporary next (saved before cur.next is overwritten, or the rest of the list is lost — same trap as Day 15's delete).

Fast/slow pointers. Start two pointers at head. Move slow one step at a time, fast two steps at a time. When fast reaches the end, slow has covered exactly half the distance — it's at the middle. The same setup detects a cycle: if the list loops back on itself, fast never hits a real end. Instead, because fast gains exactly one node on slow every step once both are inside the loop, it's guaranteed to catch up and land on the exact same node as slow within one full trip around the cycle — it can't "jump over" slow, since a gain of one node per step can't skip a node entirely.

Diagram: reversing the pointers

Diagram: fast/slow finds the middle

Interactive visualization: reverse a linked list

Interactive visualization: fast/slow pointers find the middle

The code: reverse, and find the middle

function reverseList(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;   // ① save it — we're about to overwrite cur.next
    cur.next = prev;         // ② flip the pointer backward
    prev = cur;               // advance prev to where cur was
    cur = next;                // advance cur to the node we saved in step ①
  }
  return prev; // prev is the new head once cur runs off the end (becomes null)
}

function middleNode(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {   // stop if fast can't take a full 2-step move
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

Line by line:

• reverseList: const next = cur.next must run before cur.next = prev — otherwise the only reference to the rest of the list is gone the instant it's overwritten. This is Day 15's "capture before overwrite" rule, now applied inside a loop instead of once.
• The loop ends when cur becomes null — at that exact moment, prev is sitting on what used to be the last node, which is now the new head.
• middleNode's loop condition is fast && fast.next, not just fast — fast.next.next would throw if fast.next were null. This condition guarantees a full 2-step move is always safe before attempting it.
• For an odd-length list, the loop stops with fast exactly on the last node (fast.next === null). For an even-length list, it stops one step earlier (fast === null) — slow lands on the second of the two middle nodes in that case, which is the standard convention for this problem.

Dry run: reverseList on [1, 2, 3, 4, 5]

cur becomes null after iteration 5 — loop ends, return prev (node 5). Final list: 5 → 4 → 3 → 2 → 1 → NULL.

Complexity

Interview corner

• Why prefer the iterative reversal over a recursive one? Same O(n) time, but the recursive version uses O(n) call-stack space (Day 9) versus O(1) for the iterative loop — on a very long list, recursion risks a stack overflow that the loop never will.
  ⚠ Trap: don't say recursion is "simpler" without naming this cost — interviewers want to hear you weigh the trade-off, not just prefer one style.
• Why does fast/slow find the middle in one pass instead of two (count the length, then walk length/2 steps)? Both are O(n), but fast/slow does it without a second full walk — the "count then walk" approach touches the list twice; fast/slow touches it once, arriving at the answer exactly when the single pass ends.
  ↳ Common follow-up: "Can fast ever skip past slow without meeting it, in a cycle?" — no: once both pointers are inside the loop, fast gains exactly one node on slow every step, so the gap between them shrinks by exactly 1 each time — it can't jump from "2 nodes ahead" to "1 node behind" without passing through "1 node ahead" first.
• What's the classic bug in the fast/slow loop condition? Writing while (fast) instead of while (fast && fast.next) — the first crashes with a null-pointer error the moment fast lands on the last node and the code tries fast.next.next.
• How would you find where a cycle begins, not just whether one exists? After slow and fast meet inside the cycle, reset a third pointer to head and advance it and slow one step at a time — they meet exactly at the cycle's starting node. (This is Linked List Cycle II — the reasoning behind why it works is a fun rabbit hole, but the mechanical recipe above is what to reproduce in an interview.)

How to talk through it out loud: for reversal, narrate the pointer dance before touching code — "save next, flip cur's pointer backward, slide prev and cur both forward by one." For fast/slow, state the invariant — "fast always covers exactly twice the distance slow does, so when fast runs out of room, slow is exactly at the midpoint." Naming these invariants out loud is what separates "I memorized this pattern" from "I can rebuild it from scratch if I blank on the exact code."

Practice problems

function reverseList(head) {
  let prev = null, cur = head;
  while (cur) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev;
}

function hasCycle(head) {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

function reorderList(head) {
  if (!head || !head.next) return head;

  // 1. find the middle
  let slow = head, fast = head;
  while (fast.next && fast.next.next) { slow = slow.next; fast = fast.next.next; }

  // 2. reverse the second half
  let second = slow.next;
  slow.next = null;
  let prev = null;
  while (second) {
    const next = second.next;
    second.next = prev;
    prev = second;
    second = next;
  }

  // 3. merge the two halves alternately
  let first = head;
  second = prev;
  while (second) {
    const t1 = first.next, t2 = second.next;
    first.next = second;
    second.next = t1;
    first = t1;
    second = t2;
  }
  return head;
}

Quiz