Technical Interview

Home
Added Recently
Data Structures
Puzzles
Google & Microsoft
C/C++ Questions
Java Interview Questions
Quantitative Problems
Algorithms
Featured Articles
Amazon Interview Question
Compaq Interview Question
Technical Interview
Interview Process
Introduction Questions
Object Oriented
Google Pages
Fundamental Questions
Resume Tips
Links
Contact Us
Submit Question/Answer



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