juniorLinked Lists

How do you detect a cycle in a linked list?

Updated Feb 20, 2026

Short answer

Use Floyd's tortoise-and-hare: advance one pointer a single step and another two steps per iteration. If a cycle exists the fast pointer laps the slow one and they meet; if not, the fast pointer reaches the end. It runs in O(n) time with O(1) space, which is what makes it preferable to storing visited nodes in a hash set.

Deep explanation

Python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:      # BOTH checks — fast moves two steps
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False                   # fast fell off the end

Why they must meet. Once both pointers are inside the cycle, the fast one gains exactly one position per iteration on the slow one. The gap therefore shrinks by one each time and must eventually reach zero — it cannot step over, because closing by exactly one cannot skip a value. With no cycle, fast runs off the end and the loop exits.

The loop condition needs both fast and fast.next — checking only fast will dereference None on the second hop of an even-length list.

Finding the cycle's start is the follow-up and relies on a neat piece of arithmetic. Let F be the distance from head to the cycle entry, and a the distance from the entry to the meeting point. At meeting, slow has travelled F + a and fast 2(F + a), and the difference is a whole number of laps. It works out that F equals the distance from the meeting point back round to the entry. So:

Python
def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:                    # cycle confirmed
            slow = head                     # reset ONE pointer to the head
            while slow is not fast:
                slow, fast = slow.next, fast.next   # now both move ONE step
            return slow                     # the entry node
    return None

The hash-set alternative is simpler to derive under pressure and also O(n) time, but costs O(n) space. Floyd's constant space is the reason it is the expected answer.

Real-world example

A linked structure built from user-supplied parent references can accidentally form a loop, and a naive traversal hangs forever:

Python
node = head
while node:              # never terminates if a cycle exists
    process(node)
    node = node.next

Guarding first turns an infinite hang into a clean error:

Python
if has_cycle(head):
    raise ValueError(f'Cycle detected entering at {cycle_start(head).id}')

The same technique detects loops in any structure where each element has exactly one successor — a state machine, a chain of symlinks, a sequence of pointer dereferences.

Common mistakes

  • - Writing `while fast:` without also checking `fast.next`, causing a None dereference on the two-step advance.
  • - Comparing values rather than identity — two nodes may hold equal payloads without being the same node.
  • - Advancing both pointers at the same speed, so they never converge.
  • - Resetting both pointers to the head when finding the cycle start
  • exactly one moves back, and thereafter both step one at a time.
  • - Reaching for the hash-set solution and stopping there — it works, but O(n) space is the thing the question is testing you to avoid.

Follow-up questions

  • Why is the meeting guaranteed rather than merely likely?
  • How do you find the length of the cycle?
  • What are the trade-offs against the hash-set approach?
  • Where else does this technique apply?

More Linked Lists interview questions

View all →