Floyd Cycle Detection — Tortoise and Hare

Use slow (1 step) and fast (2 steps) pointers. If there is a cycle they meet inside the loop; if fast hits None, the list is acyclic.

Try this in Python

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    next: Node | None = None


def to_list(head: Node | None) -> list[int]:
    out: list[int] = []
    while head:
        out.append(head.val)
        head = head.next
    return out


def from_list(vals: list[int]) -> Node | None:
    dummy = Node(0)
    cur = dummy
    for x in vals:
        cur.next = Node(x)
        cur = cur.next
    return dummy.next


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

a = Node(1)
a.next = Node(2)
a.next.next = Node(3)
a.next.next.next = a.next
print(has_cycle(a))

Key takeaways

• Start both at head; advance inside while fast and fast.next.
• Meeting proves a cycle, not where it starts (see classic phase-2 extension).
• Python identity (is) compares nodes correctly.