Frontend Beauty
ESC

Type to search the knowledge base.

Linked List Cycle

Detect a cycle in a linked list — Set of nodes vs Floyd tortoise and hare O(1) space, plus find-entrance follow-up.

beginner3 min read
  • dsa
  • linked-list
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft

The problem

Return true if the linked list has a cycle (some node reachable again by following next).

3 → 2 → 0 → -4
    ↑         |
    └─────────┘
→ true

Brute: hash set

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;
}
Time O(n)
Space O(n)

Optimal: Floyd’s tortoise and hare

Slow moves 1, fast moves 2. If there’s a cycle they meet. If fast hits null, no cycle.

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

function hasCycle(head: ListNode | null): boolean {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
Time O(n)
Space O(1)

Why they meet

In a cycle of length C, relative speed 1 closes the gap. Standard cycle detection proof — sketch it if asked.

Follow-up: cycle entrance (LC 142)

After meeting, reset one pointer to head; both move 1 until equal → entrance.

function detectCycle(head: ListNode | null): ListNode | null {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) {
      slow = head;
      while (slow !== fast) {
        slow = slow!.next;
        fast = fast!.next;
      }
      return slow;
    }
  }
  return null;
}

Used in Find Duplicate Number as well.

Edge cases

  • Empty / single node no self-loop
  • Self-loop at head
  • Cycle not at head
  • Long acyclic list

Common mistakes

  • Comparing val instead of node identity
  • Fast moves 2 without null checks
  • Modifying list (mark visited) when read-only expected

Interview delivery

  1. Set approach first.
  2. Floyd for O(1) space.
  3. Null-safe fast.
  4. Optional entrance.
  5. Complexities.

Mental model

If you can mark nodes, a set is trivial. Without extra memory, two pointers at different speeds collide iff a cycle exists. The meeting point is not necessarily the entrance — that’s a second phase.

Complexity table

Approach Time Space Mutates?
Hash set O(n) O(n) no
Floyd O(n) O(1) no
Mark visited bit in val O(n) O(1) yes (bad)

Out-loud answer

“Detect cycle with slow/fast pointers. Advance while fast and fast.next exist; equal means cycle. O(1) space. Set is the clear O(n) space alternative. Entrance is LC 142.”

Further reading