Detecting a cycle in a linked List (Floyd’s Cycle Detection)

OK here is another very interesting interview problem which I wanted to discuss today. The problem at hand is that you are given a singly linked list and (unfortunately) it contains a cycle i.e. some node points back to an earlier node in the linked list. Your task being a software engineer is to detect if  the linked list contains a cycle.

My initial brainstorming gave me an idea that I should traverse the list and mark nodes on my way so if I reach a node that has already been marked Hurrah !! Got ya !

Lets see how this approach works. So now I need to maintain a status for every node so I updated my Node Structure as follows

Struct Node {
int data;
Node * link;
bool status;
}

Firstly I would have to initialize all nodes with status value equal to “false”

Node * temp = head;
while (temp) {
temp->status = false;
temp = temp->link;

}

Having done that now my job is very simple. I can detect the cycle as follows:

Node * current = head;
bool isCycle = false;

while (current){

if(current->status ==true){
isCycle = true;

}

current->status = true;
current=current->next;

}

The approach seems to be fine but it required us to change our original Node data structure. Supposing the interviewer wants you to come up with a solution that doesn’t change the underlying data structure than you need to figure out some other way. Let’s look at a different algorithm that achieves this.

Most of us would remember the rabbit and turtle story from our childhood where the rabbit was very quick and turtle was very slow during the race. Consider they were racing on a straight track and for sometime assume the rabbit didn’t become complacent and instead kept on running he would have reached the finish line much quicker than the turtle, however consider they were racing in a circular field and there was no finish line the rabbit would have moved ahead quickly and eventually would have crossed the turtle again after some time. Can we use this story for our help? Yes we surely can ! this algorithm is a classical example of Floyd’s Cycle Detection Algorithm or also known as Tortoise and Hare Algorithm. So if we have a cycle in our linked list than some where along the traversal the faster pointer (Hare) would meet the slower pointer (turtle) indicating we have a cycle , else the hare would reach the end of the linked list if there is no cycle. Let’s see how we can code this.

//Hare moves twice the speed of the Turtle so if we have a cycle eventually Hare would meet the turtle again.

bool isCycle(Node *head) {

Node * turtle, * Hare;

turtle=Hare=head;

while (Hare){

if(Hare>link ==turtle->link){

return true;

}

turtle = turtle->link;
Hare= Hare->link->link;

}

return false;

}

Advertisements

1 Comment »

  1. Salman Hameed said

    Hi,
    Don’t you think that the if condition in the while block right after assigning head value to Hare and turtle will always return true? Also Hare>link is a typo.

    turtle=Hare=head;

    while (Hare){

    if(Hare>link ==turtle->link){ //it will return true in the first iteration

    return true;

    }

RSS feed for comments on this post · TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: