s.thilagavathi

• Jun 28th, 2006

 

we can delete an intermediate one

alley

• Jul 2nd, 2007

 

There's an algorithm called Floyd-cycle finding algorithm.

Briefly, start from a node and traverse the list in steps of one and two using two pointers. Eventually, both the pointers will coincide if there exists a cycle in the linked list.

Sukumar Paul

 Profile Answers by Sukumar Paul 

• Aug 1st, 2010

 

There is a very wellknown algorithm (created by Robert W. Floyd).
This algorithm is called Floyd's cycle finding algorithm.It uses 2 pointers moving at different speeds to walk the linked list. Once they enter the loop they are expected to meet, which denotes that there is a loop in the linklist. This is very much similar if a tortoise and a hare will run on a circular track instead of straight track.

bool DetectLoop(node * head)
{
node * slowPtr = head;
node * fastPtr = head;

while(slowPtr  && fastPtr)
{
 fastPtr = fastPtr->next;
 if(fastPtr == slowPtr)   //check if its equal to the slow pointer
     return true;         // loop detected

 if(fastPtr == NULL)
 {
     return false;        // since fastPtr is NULL we reached the tail of the list
 }

 fastPtr = fastPtr->next; //2nd time advance the fastPtr
 if(fastPtr == slowPtr) //check if its equal to the slow pointer
     return true;      //loop detected

 slowPtr = slowPtr-next;  // advance the slow pointer only once
}
return false;                // we reach here if we reach the tail
}