How can I detect a cycle in a linked list using C++?

How can I detect a cycle in a linked list using C++?

You can use Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare algorithm. Would you like a code example?

Yes, please provide a code example.

Here's a simple implementation:

struct Node {
    int data;
    Node* next;
};

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
}

This function returns true if there's a cycle in the linked list.

What if I want to find the starting node of the cycle?

You can modify the algorithm slightly. After detecting the cycle, reset one pointer to the head and move both pointers one step at a time. The point where they meet is the start of the cycle.

Can you show me that code as well?

Sure! Here's how you can find the starting node of the cycle:

Node* detectCycleStart(Node* head) {
    Node* slow = head;
    Node* fast = head;
    bool hasCycle = false;

    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            hasCycle = true;
            break;
        }
    }

    if (!hasCycle) return nullptr;

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow; // Starting node of the cycle
}

Thanks! This is really helpful.