Fast & Slow Pointers

How to think about it

Two pointers move at different speeds (or with a fixed offset). When the fast pointer finishes, slow is at a useful position (middle, cycle entry after reset, etc.). No need to know the list length up front.

Classic results

• Cycle: if they meet, a cycle exists (Floyd).
• Middle: when fast hits the end, slow is at mid.
• Nth from end: advance fast by n, then move both until fast ends.

Complexity baseline

O(n) time, O(1) extra space. the main reason to prefer this over storing the list.

/** Fast/slow template: detect cycle (Floyd). */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

/** Fast/slow template: detect cycle (Floyd). */
export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val; this.next = next;
  }
}
export function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;
  while (fast?.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}