2-8-loop-detection Algorithm
The 2-8-loop-detection Algorithm, also known as Floyd's Tortoise and Hare algorithm, is an efficient method for detecting cycles or loops within a sequence of values or a linked list. It is particularly useful in situations where there is a need to identify if a loop exists within a data structure, and if so, find the starting point of the loop. The algorithm was devised by Robert W. Floyd and is based on the idea of using two pointers, called the tortoise and the hare, to traverse the sequence or linked list at different speeds.
The algorithm works by initializing two pointers, the tortoise and the hare, at the starting point of the sequence or linked list. The tortoise pointer moves one step at a time, while the hare pointer moves two steps at a time. As the pointers traverse the list, they will eventually meet within the loop if one exists. Upon meeting, the hare pointer is moved back to the starting point and both pointers will move at the same speed, one step at a time. The point at which the pointers meet again is the starting point of the loop. The algorithm is both time and space efficient, with a time complexity of O(n) and space complexity of O(1), making it a popular choice for loop detection in various applications.
/**
* Cracking the coding interview, edition 6
* Problem 2.8 Loop Detection
* Problem : Determine if a linkedlist has a loop. If it has a loop, find the start of loop.
* NOTE: I have followed the approach provided in book, however, once I find start of loop,
* I remove the loop. So that we can test our solution. Read comment at line 25.
*/
#include <iostream>
struct Node {
int data;
Node * next;
Node( int d ) : data{ d }, next{ nullptr } { }
};
void removeLoop( Node * loopNode, Node * head )
{
Node * ptr1 = head;
Node * ptr2 = loopNode;
while ( ptr1->next != ptr2->next ) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
//ptr2 has reached start of loop, now removing the loop.
ptr2->next = nullptr;
}
bool detectAndRemoveCycle( Node * head )
{
if ( head == nullptr) {
return false;
}
Node * fastPtr = head;
Node * slowPtr = head;
while( slowPtr && fastPtr && fastPtr->next)
{
fastPtr = fastPtr->next->next;
slowPtr = slowPtr->next;
if ( fastPtr == slowPtr ) {
removeLoop( slowPtr, head );
return true;
}
}
return false;
}
void insert( Node * & head, int data )
{
Node * newNode = new Node( data );
if ( head == nullptr ) {
head = newNode;
} else {
Node * temp = head;
while( temp->next != nullptr ) {
temp = temp->next;
}
temp->next = newNode;
}
}
void printList( Node * head )
{
while( head ) {
std::cout << head->data << "-->";
head = head->next;
}
std::cout << "NULL" << std::endl;
}
int main()
{
Node * head = nullptr;
insert( head , 1 );
insert( head , 2 );
insert( head , 3 );
insert( head , 4 );
insert( head , 5 );
std::cout << "Current List:\n";
printList( head );
std::cout << "Inserting loop, connecting 5 to 2 \n";
head->next->next->next->next->next = head->next;
std::cout << "Detecting and deleting loop\n";
detectAndRemoveCycle(head);
std::cout << "Back to the same old list\n";
printList( head );
return 0;
}
