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
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
}

7 comments:

  1. 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.

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

    ReplyDelete
  2. 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.
    It 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

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

    ReplyDelete
  4. Very good explanation and the code makes it very clear for me
    .. 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

    ReplyDelete
  5. This logic covers all scenarios...
    Good one !!!

    ReplyDelete
  6. 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.

    ReplyDelete
  7. Having 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