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

Verified

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

Verified

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?