Cycle Detection: The Tortoise and the Hare

The Problem

Given a linked list, determine whether it contains a cycle (a node whose next pointer points back to an earlier node, creating an infinite loop). A naive approach would store every visited node in a HashSet and check for repeats — but that uses O(N) extra memory. Can you do it in O(1) space?

Floyd's Cycle-Finding Algorithm

Floyd's Cycle-Finding Algorithm (also called the Tortoise and Hare algorithm) solves this with two pointers and no extra memory:

1. Initialize slow and fast both at the head.
2. In each iteration: advance slow by 1 step, advance fast by 2 steps.
3. If fast or fast.next becomes null, the list has no cycle — return False.
4. If slow == fast at any point, a cycle exists — return True.

Why does this work? Think of two runners on a circular track. The faster runner will always eventually lap the slower one — they are guaranteed to meet inside the loop. If there is no loop, the fast runner simply exits the track (reaches null).

Mathematical intuition: Once both pointers are inside the cycle, the fast pointer closes the gap by 1 node per iteration (it moves 2, slow moves 1, net gain = 1). If the cycle has length C, they will meet within C iterations of both entering the cycle.

def hasCycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

Extension — Finding the Cycle Start: After detecting a meeting point, reset one pointer to head and advance both by 1 step at a time. They will meet exactly at the cycle's entry node. This is a common follow-up question.