Floyd’s cycle detection in Python: trade a set for two pointers

Problem. A singly linked list can loop forever when a later node points back to an earlier one, so cycle detection needs a stopping rule that does not remember the whole walk.
Baseline complexity. The set-based traversal follows one link per iteration and stores each distinct node, giving expected O(n) time and O(n) auxiliary space for n reachable nodes under ordinary hashing. Hash collisions can make an individual membership lookup O(n) in the worst case, so the traversal has no unconditional worst-case linear-time bound.[5]
Solution. Floyd’s cycle algorithm keeps a slow pointer moving one node at a time and a fast pointer moving two; a meeting proves a cycle, while a null fast pointer proves the walk ended. The method compares node identity with is.[1][4]
Measured result. On this Raspberry Pi, both implementations passed the correctness cases. For cyclic lists of 1,000, 5,000 and 10,000 nodes, the minimum set-to-Floyd time ratios were 2.886x, 3.687x and 3.592x. The 10,000-node traversal peaked at 655,576 traced bytes with the set and 0 traced bytes with Floyd.

Reproduce the result

Complete code

from __future__ import annotations
import gc
import platform
import sys
import timeit
import tracemalloc
from dataclasses import dataclass
@dataclass(slots=True, eq=False)
class Node:
    value: int
    next: Node | None = None
def build_list(size: int, cycle_entry: int | None) -> Node | None:
    if size <= 0:
        return None
    nodes = [Node(index) for index in range(size)]
    for left, right in zip(nodes, nodes[1:]):
        left.next = right
    nodes[-1].next = None if cycle_entry is None else nodes[cycle_entry]
    return nodes[-size]
def has_cycle_with_set(head: Node | None) -> bool:
    seen: set[Node] = set()
    node = head
    while node is not None:
        if node in seen:
            return True
        seen.add(node)
        node = node.next
    return False
def has_cycle_floyd(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 count_set_steps(head: Node | None) -> tuple[bool, int, int]:
    seen: set[Node] = set()
    node = head
    visits = 0
    membership_checks = 0
    while node is not None:
        visits += 1
        membership_checks += 1
        if node in seen:
            return True, visits, membership_checks
        seen.add(node)
        node = node.next
    return False, visits, membership_checks
def count_floyd_steps(head: Node | None) -> tuple[bool, int, int]:
    slow = head
    fast = head
    loop_iterations = 0
    node_advances = 0
    while fast is not None and fast.next is not None:
        loop_iterations += 1
        slow = slow.next
        fast = fast.next.next
        node_advances += 3
        if slow is fast:
            return True, loop_iterations, node_advances
    return False, loop_iterations, node_advances
def peak_traced_bytes(function, head: Node | None) -> int:
    gc.collect()
    tracemalloc.start()
    function(head)
    _, peak = tracemalloc.get_traced_memory()
    tracemalloc.stop()
    return peak
def validate() -> None:
    cases = (
        (0, None, False),
        (1, None, False),
        (1, 0, True),
        (8, None, False),
        (8, 0, True),
        (8, 3, True),
        (8, 7, True),
    )
    for size, entry, expected in cases:
        head = build_list(size, entry)
        assert has_cycle_with_set(head) == expected
        assert has_cycle_floyd(head) == expected
def main() -> None:
    validate()
    print("correctness=passed")
    print(f"python={sys.version.split(' ', 1).pop(0)}")
    print(f"platform={platform.platform()}")
    print("workload=cyclic singly linked list; cycle_entry=size//2")
    print("timing=5 repeats; number=1; set group before Floyd; timeit suspends GC")
    print("memory=one traversal; tracemalloc starts immediately before call")
    for size in (1_000, 5_000, 10_000):
        head = build_list(size, size // 2)
        baseline_result = count_set_steps(head)
        floyd_result = count_floyd_steps(head)
        set_found, _, _ = count_set_steps(head)
        floyd_found, _, _ = count_floyd_steps(head)
        assert set_found is True
        assert floyd_found is True
        baseline_times = timeit.Timer(lambda: has_cycle_with_set(head)).repeat(repeat=5, number=1)
        floyd_times = timeit.Timer(lambda: has_cycle_floyd(head)).repeat(repeat=5, number=1)
        baseline_peak = peak_traced_bytes(has_cycle_with_set, head)
        floyd_peak = peak_traced_bytes(has_cycle_floyd, head)
        ratio = min(baseline_times) / min(floyd_times)
        print(f"size={size}")
        print(f"set_steps={baseline_result[1]} set_membership_checks={baseline_result[2]}")
        print(f"floyd_iterations={floyd_result[1]} floyd_node_advances={floyd_result[2]}")
        print("set_times_seconds=" + ",".join(f"{value:.9f}" for value in baseline_times))
        print("floyd_times_seconds=" + ",".join(f"{value:.9f}" for value in floyd_times))
        print(f"min_time_ratio_set_over_floyd={ratio:.3f}")
        print(f"set_peak_traced_bytes={baseline_peak}")
        print(f"floyd_peak_traced_bytes={floyd_peak}")
if __name__ == "__main__":
    main()

Output

correctness=passed
python=3.13.5
platform=Linux-6.12.47+rpt-rpi-v8-aarch64-with-glibc2.41
workload=cyclic singly linked list; cycle_entry=size//2
timing=5 repeats; number=1; set group before Floyd; timeit suspends GC
memory=one traversal; tracemalloc starts immediately before call
size=1000
set_steps=1001 set_membership_checks=1001
floyd_iterations=500 floyd_node_advances=1500
set_times_seconds=0.000250054,0.000240535,0.000238369,0.000281480,0.000237980
floyd_times_seconds=0.000087852,0.000083814,0.000083129,0.000082832,0.000082463
min_time_ratio_set_over_floyd=2.886
set_peak_traced_bytes=41176
floyd_peak_traced_bytes=0
size=5000
set_steps=5001 set_membership_checks=5001
floyd_iterations=2500 floyd_node_advances=7500
set_times_seconds=0.001105807,0.000943160,0.001491823,0.001138844,0.000945586
floyd_times_seconds=0.000262535,0.000257832,0.000256202,0.000256054,0.000255794
min_time_ratio_set_over_floyd=3.687
set_peak_traced_bytes=655576
floyd_peak_traced_bytes=0
size=10000
set_steps=10001 set_membership_checks=10001
floyd_iterations=5000 floyd_node_advances=15000
set_times_seconds=0.001927209,0.001873450,0.001926634,0.001930709,0.001803025
floyd_times_seconds=0.000518367,0.000507052,0.000549163,0.000502015,0.000508422
min_time_ratio_set_over_floyd=3.592
set_peak_traced_bytes=655576
floyd_peak_traced_bytes=0

Environment

The run used CPython 3.13.5 on Linux 6.12.47+rpt-rpi-v8, aarch64, with no third-party packages. Run the file with python3 floyd_cycle_benchmark.py from its directory. The source prints the interpreter and platform so a rerun can identify a different machine.

Methodology

The program first checks an empty list, a one-node list, an acyclic list, a self-cycle and cycles entering at the first, middle and final nodes. It performs those checks before timing anything.

For each cyclic size, the builder creates a fresh list whose final node points to size // 2. timeit.Timer.repeat takes five one-call samples for each function, with the set timer group run before the Floyd timer group. The timed calls use timeit‘s default garbage-collection suspension, and gc.collect() is called before each later memory probe. The report uses the minimum sample for each ratio, while retaining all five samples in the Output block. The timed calls also run with `timeit`’s default garbage-collection suspension; these functions do not create new reference cycles. These ratios are minima from five one-call samples with the set group timed before Floyd for each size, so they are observations for this run rather than general speedup estimates. Python’s documentation describes timeit as a tool for timing small pieces of Python code and warns that the full result vector deserves inspection rather than blind statistical treatment.[2]

The memory probe starts tracemalloc immediately before one traversal and stops it when the function returns. It therefore measures traced Python allocations made by the traversal, not the list itself, process resident memory or native allocations. The standard library describes tracemalloc as a debug tool for tracing memory blocks allocated by Python.[3]

The problem

The test data is a chain of Node objects. In an acyclic list, the final next value is None. In a cyclic list, it points to a node already encountered. The value stored in a node is irrelevant to the decision; the code must detect that the same object has been reached again.

A naive loop has no reason to stop once it enters the cycle. It needs either a record of visited objects or a different way to make progress that eventually forces two walks to meet.

Baseline complexity

has_cycle_with_set adds the current node to seen after checking membership. An acyclic list visits each reachable node once. A cycle visits every node before its entry once, then each cycle node once, and finally checks the entry again. Under ordinary hash-table behaviour, that is expected linear work and linear auxiliary storage in the number of distinct reachable nodes. A collision-heavy worst case can make membership lookup O(n), so the time bound is not unconditional.[5]

For the benchmark’s half-list cycle, the instrumented counts were 1,001 set membership checks for 1,000 nodes, 5,001 for 5,000 nodes and 10,001 for 10,000 nodes. The extra check is the repeated cycle-entry object that ends the search.

The Node class uses @dataclass(slots=True, eq=False). Disabling generated value equality leaves ordinary object identity and hashing in place, so the set records nodes rather than comparing their integer payloads. That choice matches the question being asked, but it is an interface decision worth making explicit in production code.

The solution

Floyd’s method starts slow and fast at the head. Each loop moves slow once and fast twice, then compares them with is. The two speeds are the whole trick, and the published algorithm description states those same one-step and two-step movements.[1] Python’s comparison table defines is as object identity, which is the right test here because two different nodes may carry the same value.[4]

Consider eight nodes with the last node pointing to node 3. After the first iteration the pointers are at nodes 1 and 2. They then move to 2 and 4, 3 and 6, 4 and 3, and finally 5 and 5. The meeting occurs inside the cycle. On an acyclic list, the condition fast is not None and fast.next is not None fails before the fast pointer would step past the end.

The code in this article only answers the yes-or-no question. The same first phase can be followed by a second pass if the caller needs the cycle’s entry node. That extension is part of Floyd’s usual presentation, but it would be a different function and a different benchmark.[1]

What the measurement shows

The deterministic operation counts scale as expected for this input family. Floyd uses 500 loop iterations for 1,000 nodes, 2,500 for 5,000 and 5,000 for 10,000, because the fast pointer covers two links per loop while the slow pointer covers one. The set method performs one membership check for every distinct node and one more when it sees the repeated entry.

The timing result favoured Floyd at all three tested sizes. Its minimum samples were 82.463 microseconds, 255.794 microseconds and 502.015 microseconds, compared with 237.980 microseconds, 945.586 microseconds and 1,803.025 microseconds for the set method. Those are measurements of these two Python functions on this host and input shape, not a promise about every linked-list workload.

The allocation probe points in the same direction for traversal-local storage: Floyd reported 0 traced bytes at each size, while the set reported 41,176 bytes at 1,000 nodes and 655,576 bytes at both 5,000 and 10,000 nodes. The repeated 655,576-byte reading is a reminder that a single tracemalloc peak is not a memory-growth law. It captures Python allocations under this run’s allocator state and excludes the pre-built list.[3]

Where it stops helping

Floyd is a good fit when the structure is a deterministic next-pointer chain and the only question is whether a node repeats. It is also useful when auxiliary memory matters more than the small bookkeeping cost of two pointer variables.

A visited set is clearer when the structure branches, when the program must report the route that was visited, or when the definition of repetition is based on a value rather than object identity. It is also the safer general tool for arbitrary graph traversal, where two pointers cannot represent all reachable branches.

The benchmark does not measure cycle-entry recovery, acyclic timing, large object payloads, different cycle positions or alternative Python implementations. It also does not measure process RSS. Those omissions matter: theoretical O(1) auxiliary space describes the algorithm’s pointer state, while the Python process still contains the linked-list objects and the interpreter itself.

For a production API, define what None, an empty input and malformed links mean before choosing the implementation. Floyd’s guard prevents a normal acyclic walk from dereferencing past the end, but it cannot repair a corrupted object graph or decide whether a repeated value should count as a repeated node.

Sources

[1] Tortoise and Hare Algorithm (Linked List cycle detection)

[2] timeit — Measure execution time of small code snippets

[3] tracemalloc — Trace memory allocations

[4] Built-in Types

[5] Python Wiki: TimeComplexity