Cycle detection (Floyd's)

Decide whether a linked list loops back on itself, without storing the nodes you have visited.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Send a slow runner and a fast runner around the list. If there is a loop, the fast one laps the slow one and they land on the same node. If there is no loop, the fast one simply reaches the end.

Code

C++PythonC#

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

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

public static bool HasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

Tips

Inside the loop the gap between them shrinks by one node per step, so they must meet.
The HashSet version is simpler but uses O(n) memory.

In the .NET library

slow == fast compares references for class types, which is exactly "are these the same node?". Values are not compared.