A singly linked list contains a cycle when traversing the next pointers leads back to a previously visited node. This occurs when the tail node’s next field points not to NULL, but to some node earlier in the list—including possibly itself.

Cycle Detection Using Floyd’s Tortoise and Hare Algorithm

To determine whether a cycle exists, initialize two pointers—slow and fast—both starting at the head. The slow pointer advances one node per iteration; the fast pointer advances two nodes.

If a cycle is present, the two pointers must eventually meet inside it. If no cycle exists, fast will reach the end (NULL) first.

bool hasCycle(struct ListNode* head) {
    if (!head || !head->next) return false;

    struct ListNode* slow = head;
    struct ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }

    return false;
}

The loop condition fast && fast->next ensures safe dereferencing: fast->next->next is only accessed when both fast and fast->next are non-NULL. This handles both even- and odd-length acyclic lists uniformly.

Why Two Steps? A Formal Justification

Let the distance from head to cycle entrance be L, the cycle length be C, and the distance from entrance to meeting point be X. When slow enters the cycle, fast has already traveeld L + X + k*C for some k ≥ 0.

Since fast moves twice as fast:

2(L + X) = L + X + n*C   (for some n ≥ 1)
⇒ L + X = n*C
⇒ L = n*C − X
⇒ L ≡ (C − X) (mod C)

Thus, moving one pointer from head and another from the meeting point—both one step at a time—guarantees they converge at the cycle entrance after exactly L steps.

Using step sizes other than 2 (e.g., fast advances by 3) does not guarantee meeting for arbitrary C and initial offset. For example, if fast gains 2 positions per step and C is even while the initial gap is odd, they may never align—only periodic alignment is ensured, not guaranteed convergence.

Finding the Cycle Entrance

Once a meeting point is found, reset one pointer to the head and advance both pointers one step at a time. Their next intersection is the cycle’s starting node.

struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;

    // First phase: detect cycle
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break;
    }

    if (!fast || !fast->next) return NULL; // No cycle

    // Second phase: locate entrance
    struct ListNode* probe = head;
    while (probe != slow) {
        probe = probe->next;
        slow = slow->next;
    }

    return probe;
}

This approach uses constant space and runs in O(n) time, where n is the number of nodes.