Day 16: Linked Lists II — Fast/Slow & Reverse

DAY 16 / 30 · WEEK 3

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.

Diagrams

Reversing the pointers — mid-reversal snapshot

Fast/slow finds the middle — one pass over the list

Interactive visualization

Interactive visualization: reverse a linked list

reversed portioncur (being flipped now)

Running example: [1, 2, 3, 4, 5] → [5, 4, 3, 2, 1]

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

Interactive visualization: fast/slow pointers find the middle

slow (1 step)fast (2 steps)middle found

Running example: [1, 2, 3, 4, 5] — fast moves 2x speed

Press Play or Step to begin.

Step 0 / 0

▶ PlayStep ⏭⟲ Reset🔀 Shuffle

Code

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]

Iteration	next (saved)	cur.next = prev	prev	cur
1	2	1 → NULL	1	2
2	3	2 → 1	2	3
3	4	3 → 2	3	4
4	5	4 → 3	4	5
5	null	5 → 4	5	null

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

Complexity

Operation	Time	Space	Why
Reverse (iterative)	O(n)	O(1)	One pass, three pointer variables — no extra list, no call stack growth.
Reverse (recursive)	O(n)	O(n)	Same number of steps, but each recursive call adds a stack frame (Day 9) — n frames deep at the bottom.
Find middle (fast/slow)	O(n)	O(1)	One pass — no need to count the length first and walk again.
Cycle detection (Floyd’s)	O(n)	O(1)	Same two pointers; no hash set of visited nodes needed, unlike the O(n)-space alternative.

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.

  Caution

  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.

  Note

  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

1. Reverse Linked List

Easy — LeetCode: Reverse Linked List

Reverse a singly linked list and return the new head — today’s core technique, applied directly.

Hint: Three pointers: prev, cur, next. Save cur.next before you overwrite it — same rule as Day 15’s delete.

Solution:

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

2. Linked List Cycle

Easy — LeetCode: Linked List Cycle

Given the head of a linked list, determine if it contains a cycle, using O(1) extra space.

Hint: Floyd’s fast/slow pointers. If there’s no cycle, fast reaches a real null end. If there is one, fast and slow are guaranteed to land on the same node eventually — that’s your signal.

Solution:

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;
}

3. Reorder List

Medium — LeetCode: Reorder List

Given 1 → 2 → 3 → 4, reorder it in place to 1 → 4 → 2 → 3 — alternating from the front and back toward the middle. Combines both of today’s techniques.

Hint: Three steps: (1) find the middle with fast/slow, (2) reverse the second half with today’s three-pointer technique, (3) merge the first half and the reversed second half by alternating nodes one at a time.

Solution:

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

Quiz: 1. In the reversal loop, why must next be saved before cur.next = prev runs?

Otherwise the rest of the original list becomes permanently unreachable

Quiz: 2. What’s the advantage of fast/slow pointers over “count the length, then walk halfway”?

It finds the middle in a single pass instead of two separate walks

Quiz: 3. Why can’t fast “jump over” slow without ever meeting it, once both are inside a cycle?

Fast gains exactly one node on slow per step, so the gap shrinks by exactly 1 each time — it can’t skip a value

Quiz: 4. What’s the space-complexity trade-off between iterative and recursive list reversal?

Recursive uses O(n) call-stack space; iterative uses O(1)

Quiz: 5. Which two techniques does Reorder List combine?

Fast/slow (to find the middle) and reversal (on the second half)