Patterns

Slow advances 1 step, fast advances 2 — Floyd's cycle detection style

When to useCycle detection, find middle, find nth from end

iterative

INITIALIZE

slow = head, fast = head (or dummy)

const dummy = { val: 0, next: head };
let prev = dummy;

let slow = n;
let fast = sumSquares(n);

let slow = head; let fast = head;

let slow = head; let fast = head;

—

let slow = head; let fast = head;

—

TRAVERSE

while (fast && fast.next)

—

while (fast !== 1 && slow !== fast) {

while (fast !== null && fast.next !== null) {

while (fast !== null && fast.next !== null) {

—

while (fast && fast.next) {

—

advance

slow = slow.next; fast = fast.next.next

  prev = prev.next;

  slow = sumSquares(slow);
  fast = sumSquares(sumSquares(fast));

  slow = slow.next;
  fast = fast.next.next;

  slow = slow.next;
  fast = fast.next.next;

—

  slow = slow.next;
  fast = fast.next.next;

—

[DECIDE]

check meeting condition or pointer state

prev.next = prev.next.next;

—

  if (slow === fast) return true;

  if (slow === fast) {
    let size = 1; let curr = slow.next;
    while (curr !== slow) { curr = curr.next; size++; }
    return size;
  }

—

RETURN

slow (or derived value)

return dummy.next;

return fast === 1;

return false;

return -1;

—

return slow.val;

—