How to Detect Cycle in Linked List in C++

To detect a cycle in a linked list in C++, use Floyd’s Cycle Detection algorithm, also called the tortoise and hare method. It uses two pointers moving at different speeds; if they meet, a cycle exists. This approach is efficient with O(n) time and O(1) space complexity.

Syntax

The main idea is to use two pointers: slow moves one step at a time, and fast moves two steps at a time. If the linked list has a cycle, these pointers will eventually meet inside the cycle.

Here is the basic syntax pattern:

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true; // cycle detected
        }
    }
    return false; // no cycle
}

Explanation:

• slow and fast start at the list head.
• fast moves twice as fast as slow.
• If fast reaches the end (nullptr), no cycle exists.
• If slow and fast meet, a cycle is present.

cpp

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

Example

This example creates a linked list with a cycle and uses the hasCycle function to detect it. It prints Cycle detected if a cycle exists, otherwise No cycle.

cpp

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

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

int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    // Create a cycle: point next of last node to second node
    head->next->next->next->next = head->next;

    if (hasCycle(head)) {
        std::cout << "Cycle detected" << std::endl;
    } else {
        std::cout << "No cycle" << std::endl;
    }

    // Note: In real code, free memory carefully to avoid leaks
    return 0;
}

Output

Cycle detected

Common Pitfalls

• Not checking if fast or fast->next is nullptr before advancing fast causes runtime errors.
• Using only one pointer or moving both pointers at the same speed will not detect cycles efficiently.
• Forgetting to handle empty lists (head == nullptr) can cause errors.

Wrong approach example:

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr) { // Missing fast->next check
        slow = slow->next;
        fast = fast->next->next; // May cause crash if fast->next is nullptr
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Correct approach: Always check fast != nullptr && fast->next != nullptr in the loop condition.

cpp

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

Quick Reference

• Use two pointers: slow moves 1 step, fast moves 2 steps.
• Check fast != nullptr && fast->next != nullptr before moving pointers.
• If slow == fast, a cycle exists.
• Return true if cycle found, else false.

Key Takeaways

Use Floyd’s Cycle Detection algorithm with two pointers moving at different speeds to detect cycles.

Always check that pointers are not null before advancing to avoid crashes.

If the two pointers meet, a cycle exists in the linked list.

Return false if the fast pointer reaches the end of the list, meaning no cycle.

This method runs in linear time and uses constant extra space.