# 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:

- 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) {}
};

public:

void push(int data) {
Node* newNode = new Node(data);
}

// Function to detect loop using Floyd’s cycle-finding algorithm
bool detectLoop() {
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++;
}

// 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() {
list.push(10);
list.push(20);
list.push(30);
list.push(40);

// Creating a loop for testing

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.