Cycle Detection

Floyd's Cycle Detection

A cycle in a linked list means some node's next pointer points back to an earlier node, creating an infinite loop. Traversing such a list with a simple while (cur != NULL) would never terminate.

[1] -> [2] -> [3] -> [4] -> [5]
              ^                |
              |________________|

The Tortoise and Hare Algorithm

Floyd's algorithm uses two pointers moving at different speeds:

• Slow (tortoise): moves one step at a time
• Fast (hare): moves two steps at a time

If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet inside the cycle. If there is no cycle, the fast pointer reaches NULL.

int has_cycle(struct Node *head) {
    struct Node *slow = head;
    struct Node *fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

Why Does It Work?

Once both pointers are inside the cycle, the distance between them shrinks by 1 on every iteration (fast gains one step, but they are in a loop). So they are guaranteed to collide.

Time & Space Complexity

• Time: O(n) — the pointers meet within at most one full traversal of the cycle
• Space: O(1) — only two pointers, no extra data structures

Your Task

Implement int has_cycle(struct Node *head) that returns 1 if the list contains a cycle, and 0 otherwise.