Loop Detection in a Linked List – C++ Program

This program demonstrates how to detect a loop in a singly linked list using Floyd’s Cycle-Finding Algorithm, also known as the “Tortoise and Hare” algorithm. The algorithm is efficient, operating with a time complexity of O(n) and a space complexity of O(1).

Program Structure

1. Node Structure:We first define the structure of a node in the linked list. Each node has an integer data field and a pointer to the next node.
2. Function to Detect a Loop:The function detectLoop implements Floyd’s Cycle-Finding Algorithm. It uses two pointers, slow and fast, which move through the list at different speeds. If there’s a loop, these pointers will eventually meet.
3. Main Function:In the main function, we create a linked list, manually introduce a loop, and then call detectLoop to check for the presence of a loop.

C++ Program

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

// Function to detect loop in the linked list
bool detectLoop(Node* head) {
    Node* slow = head;
    Node* fast = head;

    while (slow && fast && fast->next) {
        slow = slow->next;         // Move slow pointer by one
        fast = fast->next->next;   // Move fast pointer by two

        // If slow and fast meet at the same point, there is a loop
        if (slow == fast) {
            return true;
        }
    }
    // No loop found
    return false;
}

int main() {
    // Creating a linked list
    Node* head = new Node();
    Node* second = new Node();
    Node* third = new Node();
    Node* fourth = new Node();

    head->data = 1;
    head->next = second;

    second->data = 2;
    second->next = third;

    third->data = 3;
    third->next = fourth;

    fourth->data = 4;
    fourth->next = second;  // Creating a loop for testing

    // Detecting loop in the linked list
    if (detectLoop(head)) {
        std::cout << "Loop detected in the linked list." << std::endl;
    } else {
        std::cout << "No loop detected in the linked list." << std::endl;
    }

    // Note: In a real-world scenario, we should also free the allocated memory.
    return 0;
}

Explanation

The detectLoop function is designed to determine whether a loop exists in a linked list:

• Two pointers, slow and fast, are initialized to the head of the list.
• The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
• If there is no loop, the fast pointer will reach the end of the list (i.e., it will become NULL).
• If a loop exists, the slow and fast pointers will eventually meet within the loop.
• When the two pointers meet, the function returns true, indicating the presence of a loop.
• If the fast pointer reaches the end of the list, the function returns false, indicating that there is no loop.

This method is efficient and widely used in detecting loops in linked lists.