Detecting a Cycle (Floyd’s Algorithm)

A linked list is supposed to end at None, but a bug in how nodes are wired together — or an intentionally circular structure — can make some node’s next pointer loop back to an earlier node, so the list never terminates. Floyd’s Cycle Detection Algorithm, nicknamed the “tortoise and hare”, answers the question “does this linked list contain a cycle?” using only two pointers and no extra memory. It is one of the most-asked patterns in coding interviews, and the same two-pointer trick generalizes far beyond linked lists to any process that repeatedly maps one state to the next.

Overview: How Floyd’s Cycle Detection Works

Picture debugging a cache implemented as a linked list. You call a function that walks the list printing every value, and it never returns — it just hangs. That is the classic symptom of a cycle: instead of the last node’s next being None, it points back to an earlier node, so a naive walk loops forever: B -> C -> D -> B -> C -> D -> ....

Floyd’s algorithm detects this with two pointers, conventionally called slow and fast, that both start at the head. On every iteration, slow advances one node (slow = slow.next) and fast advances two nodes (fast = fast.next.next). Think of it like two runners on a track: if the track is a straight line with an end, the faster runner reaches the end first and the race simply stops. But if the track loops around, the faster runner eventually laps the slower one — they end up standing on the exact same spot at the same time, even though they started together and move at different speeds.

Why the pointers are guaranteed to meet

If there is no cycle, the list is a finite line, and fast (moving twice as fast) reaches the end and becomes None before or at the same time as slow. Checking fast is not None and fast.next is not None before each step both advances the pointers safely and detects this termination.

If there is a cycle, once slow enters the cycle, fast is already inside it (since fast is always at least as far along as slow). From that point on, every iteration fast gains one extra position on slow relative to the cycle (it moves 2 steps to slow‘s 1, a net gain of 1 per iteration). Since they are both moving around a loop of some fixed length k, the gap between them — measured around the loop — shrinks by exactly 1 each iteration. A shrinking gap in a finite loop must eventually hit 0, meaning the two pointers land on the identical node. That is the moment slow is fast becomes true, and it is guaranteed to happen within at most k iterations of slow entering the cycle.

Time and Space Complexity

The dominant cost is the traversal itself. In the worst case (a cycle that starts near the end of a long list, or no cycle at all), fast and slow together visit each node a bounded, constant number of times, so the work is linear in the number of nodes n. Because the algorithm only ever keeps two pointers, memory use does not grow with input size.

Approach	Time	Space	Notes
Floyd’s algorithm (tortoise & hare)	O(n)	O(1)	Two pointers, no extra data structure.
Hash set of visited nodes	O(n)	O(n)	Simpler to reason about, but stores every visited node.
Finding the cycle’s start node	O(n)	O(1)	Reuses the meeting point from Floyd’s algorithm plus one more pointer from the head.

Why O(n) and not something larger? Before any meeting happens, fast cannot take more than roughly 2n steps total: either it runs off the end of a finite list (proving no cycle, in at most n iterations) or it is bounded inside a cycle of length at most n, where a meeting is forced within another n iterations at most. Dropping constants, that is O(n) time. Space is O(1) because slow, fast, and (for finding the start) one more pointer are the only variables used, regardless of how many nodes the list has.

Examples

Example 1: A list with no cycle

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def has_cycle(head: "Node | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


def build_list(values: list[int]) -> "Node | None":
    head = None
    tail = None
    for value in values:
        node = Node(value)
        if head is None:
            head = node
            tail = node
        else:
            tail.next = node
            tail = node
    return head


first_list = build_list([1, 2, 3, 4, 5])
print(has_cycle(first_list))

Output:

False

The list is 1 -> 2 -> 3 -> 4 -> 5 -> None. Each iteration slow and fast move to different nodes (they are never equal), and once fast reaches node 5, fast.next is None, so the loop condition fails and the function returns False.

Example 2: A list with a genuine cycle

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def has_cycle(head: "Node | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False


node_a = Node("a")
node_b = Node("b")
node_c = Node("c")
node_d = Node("d")
node_a.next = node_b
node_b.next = node_c
node_c.next = node_d
node_d.next = node_b  # node_d points back to node_b, creating a cycle

print(has_cycle(node_a))

Output:

True

Here d‘s next points back to b, forming a cycle b -> c -> d -> b -> .... Tracing it: after iteration 1, slow is at b and fast is at c. After iteration 2, slow is at c and fast has wrapped to b. After iteration 3, slow reaches d and fast also lands on d — they match, so the function returns True.

Example 3: Finding where the cycle begins

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def find_cycle_start(head: "Node | None") -> "Node | None":
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            pointer = head
            while pointer is not slow:
                pointer = pointer.next
                slow = slow.next
            return pointer
    return None


node_3 = Node(3)
node_2 = Node(2)
node_0 = Node(0)
node_neg4 = Node(-4)
node_3.next = node_2
node_2.next = node_0
node_0.next = node_neg4
node_neg4.next = node_2  # cycle starts at node_2

start = find_cycle_start(node_3)
print(start.value if start is not None else None)

Output:

2

This is a classic extension of the algorithm. Once slow and fast meet inside the cycle (at node -4 here), resetting a new pointer to head and advancing it one step at a time alongside slow (also one step at a time) makes them meet exactly at the first node of the cycle, node 2. This works because of the arithmetic relationship between the distance to the cycle start and the distance the pointers travel before meeting — it always works out so that walking the same number of steps from the head and from the meeting point lands on the same node: the cycle’s entrance.

How It Works Step by Step

Trace has_cycle (and implicitly the meeting point used by find_cycle_start) on the list from Example 3: 3 -> 2 -> 0 -> -4 -> back to 2.

Step	slow	fast	Met?
Start	3	3	—
1	2	0	No
2	0	2	No
3	-4	-4	Yes

They meet at node -4 after three iterations. To find the cycle’s start, a new pointer begins at the head (3) while slow stays at the meeting point (-4). Both then advance one step at a time: the head pointer moves to 2, and slow moves from -4 to 2 (following the cycle edge). They land on the same node, 2, which is exactly the cycle’s entry point.

Common Mistakes

Mistake 1: Comparing values instead of node identity

It is tempting to compare .value fields instead of the node objects themselves. This is wrong: two different nodes can legitimately hold the same value without being part of a cycle, which produces a false positive.

def has_cycle_buggy(head: "Node | None") -> bool:
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow.value == fast.value:  # bug: compares values, not the nodes themselves
            return True
    return False

The fix is to compare identity with is, which checks whether slow and fast refer to the exact same object in memory, not merely equal-looking data:

if slow is fast:
    return True

Mistake 2: Checking fast.next before confirming fast is not None

Python’s and short-circuits left to right, so the order of the loop condition matters. Writing the check backwards accesses .next on a None object and crashes.

def has_cycle_buggy(head: "Node | None") -> bool:
    slow = head
    fast = head
    while fast.next is not None and fast is not None:  # wrong order: checks fast.next before fast
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

When fast eventually becomes None (in a list with no cycle), evaluating fast.next raises AttributeError: 'NoneType' object has no attribute 'next' before the second half of the condition ever runs. The fix is to put the None check first, so the short-circuit protects the attribute access: while fast is not None and fast.next is not None:.

Mistake 3: Storing values instead of node identity in a hash set

A common alternative to Floyd’s algorithm tracks visited nodes in a set. Storing raw values instead of the nodes themselves reintroduces the same false-positive bug as Mistake 1.

def has_cycle_with_set_buggy(head: "Node | None") -> bool:
    seen_values = set()
    current = head
    while current is not None:
        if current.value in seen_values:  # bug: two different nodes can share a value
            return True
        seen_values.add(current.value)
        current = current.next
    return False

The corrected version stores the node objects themselves. Because Node does not define a custom __eq__ or __hash__, Python’s default identity-based hashing applies, so membership testing correctly distinguishes two different nodes that happen to hold equal values:

class Node:
    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


def has_cycle_with_set(head: "Node | None") -> bool:
    seen_nodes = set()
    current = head
    while current is not None:
        if current in seen_nodes:
            return True
        seen_nodes.add(current)
        current = current.next
    return False


node_x = Node(5)
node_y = Node(5)  # same value as node_x, but a different node object
node_x.next = node_y

print(has_cycle_with_set(node_x))

Output:

False

Even though node_x and node_y share the value 5, they are distinct objects with no cycle between them, and the corrected function correctly reports False.

Best Practices

• Prefer Floyd’s algorithm (O(1) space) over a hash set of visited nodes (O(n) space) whenever memory matters — which is almost always the point of cycle detection in the first place.
• Always check fast is not None before fast.next is not None, in that order, so and‘s short-circuiting protects you from an AttributeError.
• Compare nodes with is, never == or by comparing .value, unless the class defines a trustworthy custom __eq__ — identity, not equal-looking data, is what defines “the same node”.
• If you need the cycle’s start node or its length, extend the same meeting point rather than writing a second full traversal from scratch; it stays O(n) time and O(1) space.
• In interviews, it is fine to mention the hash-set approach as the straightforward O(n)-space baseline before optimizing to Floyd’s algorithm — showing you recognize the space trade-off is often what’s being evaluated.
• Remember that the tortoise-and-hare technique isn’t limited to linked lists — it applies to any process that deterministically maps a state to a next state (for example, detecting whether repeatedly summing the squares of a number’s digits ever loops without reaching 1).

Practice Exercises

1. Write a function cycle_length(head: "Node | None") -> int that returns the length of the cycle in a linked list, or 0 if there is none. Hint: once slow and fast meet inside the cycle, keep one pointer fixed and advance a second pointer one step at a time, counting steps until it returns to the fixed pointer.
2. Implement is_happy(n: int) -> bool using the tortoise-and-hare technique on a number sequence instead of a linked list: repeatedly replace a number with the sum of the squares of its digits; the number is “happy” if this process reaches 1, and “unhappy” if it enters a cycle that never includes 1. For n = 19, the expected result is True.
3. Given the head of a linked list, write is_palindrome(head: "Node | None") -> bool using O(1) extra space. Hint: use slow/fast pointers to find the middle of the list, reverse the second half in place, then compare the two halves node by node.

Summary

• Floyd’s algorithm (tortoise and hare) detects a cycle in a linked list with two pointers moving at different speeds: slow advances one node per step, fast advances two.
• If there is no cycle, fast reaches None and the search ends cleanly; if there is a cycle, the gap between slow and fast shrinks by one position each iteration, guaranteeing they meet inside the loop.
• Time complexity is O(n) and space complexity is O(1) — the key advantage over a hash-set approach, which is O(n) time and O(n) space.
• The same meeting point can locate exactly where the cycle begins, in additional O(n) time and O(1) space, by walking one pointer from the head and one from the meeting point at equal speed.
• The two most common bugs are checking fast.next before confirming fast is not None, and comparing nodes by value instead of by identity with is.