Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Linked List Cycle

Problem (restated)

Given head of a linked list, return true if there is a cycle.

Intuition

Floyd: slow moves 1, fast moves 2. If they meet, a cycle exists. If fast hits null, no cycle.

Approaches

Floyd cycle detection

Unverified

Time O(n)Space O(1)

Idea. slow=fast=head; while fast and fast.next: advance; if equal return true.

Walkthrough. Cycle of length k: fast gains one node per step inside the cycle and eventually lands on slow.

Trade-offs. O(1) space beats a HashSet of visited nodes (O(n) space).

Solution

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

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

Hash set of nodes

Unverified

Time O(n)Space O(n)

Idea. Insert each node into a set; if seen again, cycle.

Walkthrough. Walk list; second visit of any node ⇒ true.

Trade-offs. Simpler mentally; uses linear memory and may be disallowed if mutation-free O(1) space is required.

Solution

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function hasCycleSet(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  let cur = head;
  while (cur) {
    if (seen.has(cur)) return true;
    seen.add(cur);
    cur = cur.next;
  }
  return false;
}

export class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

export function hasCycleSet(head: ListNode | null): boolean {
  const seen = new Set<ListNode>();
  let cur = head;
  while (cur) {
    if (seen.has(cur)) return true;
    seen.add(cur);
    cur = cur.next;
  }
  return false;
}

Template connection

Canonical fast & slow cycle detection.

Reflection

Floyd: slow moves +1, fast moves +2. Fast falling off to null means no cycle. Do you compare the pointers at the start of the step or the end?
A one-node self-loop, and a two-node cycle: does fast skip the meeting on the first step?
You want O(1) extra memory and you must not mutate the list. What do you give up versus a set of nodes?