Detect Cycle in Linked List Floyd's Algorithm in DSA C

Mental Model

Use two pointers moving at different speeds to find if a loop exists in a linked list.

Analogy: Imagine two runners on a circular track: one runs fast, the other slow. If the track loops, the fast runner will eventually catch the slow runner.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5, with a cycle from node 5 back to node 3

Goal: Detect if the linked list contains a cycle using Floyd's algorithm

Step 1: Initialize slow and fast pointers at head (node 1)

1 -> 2 -> 3 -> 4 -> 5 ->
          ↑slow, ↑fast (both at node 1)

Why: Start both pointers at the beginning to begin traversal

Step 2: Move slow by 1 step to node 2, fast by 2 steps to node 3

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast
          ↑slow

Why: Advance pointers at different speeds to detect cycle

Step 3: Move slow by 1 step to node 3, fast by 2 steps to node 5

1 -> 2 -> 3 -> 4 -> 5 ->
                    ↑fast
               ↑slow

Why: Continue advancing pointers; fast moves twice as fast

Step 4: Move slow by 1 step to node 4, fast by 2 steps from node 5 to node 4 (due to cycle)

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast, ↑slow

Why: Fast pointer loops back due to cycle; pointers meet

Step 5: Pointers slow and fast meet at node 4, cycle detected

1 -> 2 -> 3 -> 4 -> 5 ->
               ↑fast, ↑slow (meeting point)

Why: Meeting point confirms presence of cycle

Result:

1 -> 2 -> 3 -> 4 -> 5 -> (cycle back to 3)
Cycle detected: true

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for singly linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to detect cycle using Floyd's algorithm
int detectCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // move slow by 1
        fast = fast->next->next; // move fast by 2

        if (slow == fast) {
            return 1; // cycle detected
        }
    }
    return 0; // no cycle
}

// Helper function to print list up to 10 nodes to avoid infinite loop
void printList(Node* head) {
    Node* temp = head;
    int count = 0;
    while (temp != NULL && count < 10) {
        printf("%d -> ", temp->data);
        temp = temp->next;
        count++;
    }
    if (temp != NULL) {
        printf("... (cycle detected)\n");
    } else {
        printf("null\n");
    }
}

int main() {
    // Create nodes
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    // Create cycle: node 5 points back to node 3
    head->next->next->next->next->next = head->next->next;

    // Print list (limited)
    printList(head);

    // Detect cycle
    int hasCycle = detectCycle(head);
    if (hasCycle) {
        printf("Cycle detected: true\n");
    } else {
        printf("Cycle detected: false\n");
    }

    return 0;
}

while (fast != NULL && fast->next != NULL) {

continue loop while fast pointer and its next exist to avoid null dereference

slow = slow->next; // move slow by 1

advance slow pointer by one node

fast = fast->next->next; // move fast by 2

advance fast pointer by two nodes

if (slow == fast) { return 1; }

if pointers meet, cycle exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> ... (cycle detected)

Cycle detected: true

Complexity Analysis

Time: O(n) because both pointers traverse the list at most once until they meet or reach the end

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Compared to using a hash set to store visited nodes (O(n) space), Floyd's algorithm uses constant space making it more efficient

Edge Cases

Empty list (head is NULL)

Function returns no cycle immediately

DSA C

while (fast != NULL && fast->next != NULL) {

Single node with no cycle

Function returns no cycle as fast or fast->next is NULL

DSA C

while (fast != NULL && fast->next != NULL) {

Cycle at the beginning (node 1 points to itself)

Pointers meet quickly and cycle detected

DSA C

if (slow == fast) { return 1; }

When to Use This Pattern

When you need to check if a linked list loops back on itself, use Floyd's cycle detection because it finds cycles efficiently with two pointers moving at different speeds.

Common Mistakes

Mistake: Not checking if fast or fast->next is NULL before advancing fast pointer
Fix: Add condition 'while (fast != NULL && fast->next != NULL)' to avoid null pointer errors

Mistake: Moving slow and fast pointers by the same amount
Fix: Move slow by one step and fast by two steps to detect cycle properly

Summary

Detects if a linked list has a cycle by using two pointers moving at different speeds.

Use when you want to find if a linked list loops back on itself without extra memory.

The fast pointer will catch the slow pointer if a cycle exists, like runners on a circular track.