C++ Program to Detect and Remove Loop in a Linked List

1. Introduction

Detecting and removing a loop in a linked list is a classic problem in computer science. A loop in a linked list means that traversing the list will lead to an infinite loop. These loops can arise accidentally in certain operations, and it's vital to detect and remove them to ensure the list functions correctly. This blog post walks you through a C++ program that uses Floyd's Cycle-Finding algorithm, also known as the "tortoise and the hare" approach, to detect and remove such loops.

2. Program Overview

The program will:

1. Implement a linked list with methods for:

- Adding nodes.

- Detecting a loop.

- Removing the loop.

2. Utilize the "tortoise and hare" approach to detect and subsequently remove the loop.

3. Demonstrate the implementation in a main program.

3. Code Program

#include<iostream>
using namespace std;

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

class LinkedList {
public:
    Node* head;
    LinkedList() : head(nullptr) {}

    void push(int data) {
        Node* newNode = new Node(data);
        newNode->next = head;
        head = newNode;
    }

    // Function to detect loop using Floyd’s cycle-finding algorithm
    bool detectLoop() {
        Node* slow = head;
        Node* fast = head;
        while (slow && fast && fast->next) {
            slow = slow->next;           // Move slow by one step
            fast = fast->next->next;     // Move fast by two steps
            if (slow == fast) {          // If they meet, then loop exists
                removeLoop(slow);        // Call the function to remove loop
                return true;
            }
        }
        return false;
    }

    // Function to remove loop
    void removeLoop(Node* loopNode) {
        Node* ptr1 = loopNode;
        Node* ptr2 = loopNode;

        // Count the number of nodes in the loop
        int k = 1;
        while (ptr1->next != ptr2) {
            ptr1 = ptr1->next;
            k++;
        }

        ptr1 = head;

        // Move ptr2 to k nodes ahead
        while (k--) {
            ptr2 = ptr2->next;
        }

        // Move both pointers at same pace, they'll meet at loop start
        while (ptr2 != ptr1) {
            ptr1 = ptr1->next;
            ptr2 = ptr2->next;
        }

        // Move ptr2 to the last node
        while (ptr2->next != ptr1) {
            ptr2 = ptr2->next;
        }

        ptr2->next = nullptr;  // Break the loop
    }

};

int main() {
    LinkedList list;
    list.push(10);
    list.push(20);
    list.push(30);
    list.push(40);

    // Creating a loop for testing
    list.head->next->next->next->next = list.head->next;

    if (list.detectLoop())
        cout << "Loop detected and removed!" << endl;
    else
        cout << "No loop detected." << endl;

    return 0;
}

Output:

Loop detected and removed!

4. Step By Step Explanation

1. A Node class is utilized to define each node of the linked list, and the LinkedList class provides methods to manipulate the list.

2. The push method adds a new node to the start of the list.

3. The detectLoop method employs Floyd’s cycle-finding algorithm. It uses two pointers (often termed as tortoise and hare). While traversing the list, if there's a loop, the two pointers will eventually meet.

4. Once a loop is detected, the removeLoop method is invoked. It first determines the number of nodes in the loop. Next, by using two pointers, it identifies the starting node of the loop. One of the pointers is then moved through the loop to reach the last node, and the loop is broken.

5. The program ends by demonstrating the loop detection and removal process.

The included comments further elucidate each step of the process.