Fast and Slow Pointers

// Template 1: find the middle. fast moves two nodes for every one that slow moves,
// so slow is half way along when fast runs out of list.
export function middleNode(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) { // even length: slow ends on the second middle
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// Variant for splitting a non-empty list: the last node of the first half (the first middle on even lengths).
export function endOfFirstHalf(head) {
  let slow = head;
  let fast = head;
  while (fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
}

// Template 2: Floyd's cycle detection. Inside a loop, fast gains exactly one node per step on slow,
// so it can't jump over it: they meet. Without a loop, fast falls off the end.
export function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true; // the same node, not just an equal value
  }
  return false;
}

// Phase 2: the head and the meeting point are equally far from the cycle's entry (up to whole laps),
// so two pointers moving one step at a time from those two places meet exactly at the entry.
export function cycleStart(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let entry = head;
      while (entry !== slow) {
        entry = entry.next;
        slow = slow.next;
      }
      return entry;
    }
  }
  return null;
}

// Template 3: a cycle in an implicit sequence x0, f(x0), f(f(x0)), … Nothing is stored: f plays the role of node.next.
// Returns where the repeating part starts, how many steps lead into it (tail) and how long it is.
export function floyd(f, x0) {
  let slow = x0;
  let fast = x0;
  do {                     // phase 1: meet somewhere inside the cycle
    slow = f(slow);
    fast = f(f(fast));
  } while (slow !== fast);
  let entry = x0;          // phase 2: equal distances lead to the start of the cycle
  let tail = 0;
  while (entry !== slow) {
    entry = f(entry);
    slow = f(slow);
    tail++;
  }
  let length = 1;          // phase 3: walk once around the cycle
  for (let x = f(entry); x !== entry; x = f(x)) length++;
  return { start: entry, tail, length };
}