bool ListContainsLoop(Node * head) { Node * slowPtr = head; Node * fastPtr = head; while(slowPtr && fastPtr) { fastPtr = fastPtr->next; // advance the fast pointer if(fastPtr == slowPtr) // and 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 } fastPtr = fastPtr->next; //advance and check again if(fastPtr == slowPtr) return true; slowPtr = slowPtr-next; // advance the slow pointer only once } return false; // we reach here if we reach the tail }

### Linked List Loop/Cycle Detection

Problem: Given the head pointer to a singly linked list with a loop or cycle in it. If you were to walk this list you never arrive at the end or the tail of the linked list. Find whether the list contains a loop in O(n) time and space complexity.
Observation: A linked list with a loop will have a node that is being pointed from 2 different node.
Solution 1: This problem was solved in the late 1960s by Robert W. Floyd. The solution is aptly named as Floyd's cycle finding algorithm a.k.a the Tortoise and Hare 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. This works because the only way a faster moving pointer would point to the same location as a slower moving pointer is if somehow the entire list or a part of it is circular. Think of a tortoise and a hare running on a track. The faster running hare will catch up with the tortoise if they are running on circular track instead of a straight strip.
Code:
//returns true if the linked list contains a loop

Subscribe to:
Post Comments (Atom)

Because linked list has one next pointer points to the right of it (generally), the cycle must include the last (tail) node. Therefore there is no node whose next pointer is null. Therefore, again, I think it is enough to traverse the linked list and see whether there is a node whose next is null.

ReplyDeleteIs the thought above correct or are there problems with it?

John, You are right that the loop will include the intended tail node. But, by definition a tail node is one that has no next node (has a null next pointer). So, in the case we have a loop in the list, we do not have a tail node so to speak.

ReplyDeleteIt is not enough to just traverse the linked list and see if it has a tail node or not, because a list with a loop will not have a tail node. If we keep looping in this list we will enter an infinite loop.

But having said that, if we knew the number of nodes (n) in the list before hand we could traverse the list for n nodes and if we are not at the tail node then we can deduce that there is loop. But, most simple implementations of a linked list don't store the node count. You can talk to the interviewer and if you mutually agree, this approach can be used to solve the problem.

-gman

thanks for the answer, it is explaining....

ReplyDeleteVery good explanation and the code makes it very clear for me

ReplyDelete.. but one comment in two places

After doing "fastPtr = fastPtr->next;" the next line must be "if(fastPtr == NULL) ..." if not then the line "if(fastPtr == slowPtr)" might give null pointer expecption.

redsowrd

This logic covers all scenarios...

ReplyDeleteGood one !!!

instead of this why don't we have a flag in the structure which represents if the node traversal is done or not.This makes job easy.

ReplyDeleteHaving a flag in the structure is one way to solve it, but the interviewer will typically put the restriction that you cannot modify the structure. Otherwise, the problem is trivial.

ReplyDelete