Problem · LC 141

Linked List Cycle

Easy
◧ Foundation · slow-fast pointers (Floyd's cycle detection)

How to recognize it

A linked list that might have a cycle (a node pointing back to an earlier node, creating an infinite loop). The signal: "detect a cycle", "has a loop", or "find if there's a cycle". No array is given; you can only traverse the list.

The core idea

Use slow and fast pointers: slow advances 1 step per iteration, fast advances 2 steps. If there's a cycle, fast will eventually catch up to slow (they'll point to the same node). If fast reaches null, there's no cycle. This works because fast gains 1 node on slow each iteration.

Why It's Tricky

Detecting a cycle in a linked list is unintuitive at first: how do you know you've hit a cycle if you can't "see" the whole list? Storing all nodes in a set works but uses O(n) space. Floyd's algorithm is clever: two pointers at different speeds will collide if there's a cycle.

The Key Insight

The math: if there's a cycle of length C, then fast (moving 2 steps) gains 1 node on slow (moving 1 step) each iteration. After C iterations of gaining, fast laps slow. This is guaranteed to happen before fast goes through more than n + C nodes.

Step-by-Step Walkthrough

Example: 1→2→3→4→2 (cycle at 2)

slow=1, fast=1
slow→2, fast→3
slow→3, fast→2 (fast moved 2 steps from 1)
slow→4, fast→3
slow→2, fast→4
slow→3, fast→2
slow→4, fast→3
slow→2, fast→4
...

Eventually: slow→4, fast→4 → COLLISION! Cycle detected.

time O(n)
space O(1)
linked_list_cycle
def hasCycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Interview gotchas

  • Must handle the case where fast reaches null (no cycle): while fast and fast.next.
  • Don't compare nodes directly in languages where node identity matters; compare with is or pointer equality, not value equality.
  • This detects a cycle but doesn't find the START of the cycle (that's LC 142).
  • Off-by-one: Make sure fast has two steps available before advancing; if fast.next is null and you try fast.next.next, you'll crash.

💡 What to Say in the Interview

  • Say: "I'll use the slow-fast pointer technique (Floyd's cycle detection)."
  • Explain: "Slow moves 1 step, fast moves 2 steps. If there's a cycle, they'll collide."
  • Math insight: "In a cycle of length C, fast gains 1 node on slow per iteration. They collide within n steps."
  • Complexity: "O(n) time (visit each node at most twice), O(1) space (just two pointers)."

↳Variants they'll pivot to

Solve the base problem, then interviewers escalate. These are the usual next steps — knowing the connection is worth more than memorizing each.