Question: How would you find a loop in a singly-linked list?
Answer: This is a very typical tech interview question that has a very elegant solution that runs in O(n) time and O(1) space. Also referred to as the “Tortoise and Hare Algorithm”, the solution uses a fast pointer (traversing the list two items at a time) and a slow pointer (traversing the list one item at a time). If there is a loop, then the fast pointer will go around the loop twice as fast as the slow pointer. At one point, these two pointers will point to the same item. Here’s some code to make this clearer.
bool hasLoop( Node *startNode )
{
Node *slowNode, *fastNode;
slowNode = fastNode = startNode;
while( slowNode && fastNode && fastNode->next )
{
if( slowNode == fastNode->next || slowNode == fastNode->next->next )
{
return true;
}
slowNode = slowNode->next;
fastNode = fastNode->next->next;
}
return false;
}
Update: Thanks to RiderOfGiraffes for this solution.
The time complexity of this solution is still O(n), same as the solution provided above but this solution takes less number of steps at each point.
bool hasLoop( Node *startNode )
{
Node *tortoise, *hare;
int test_size = 2, steps_taken = 0;
tortoise = hare = startNode;
while( tortoise && hare->next )
{
hare = hare->next, steps_taken++;
if( tortoise == hare )
{
return true;
}
if ( steps_taken>=test_size )
{
steps_taken = 0, test_size *= 2;
tortoise = hare;
}
}
return false;
}
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
I constantly spent my half an hoour tto read this webpage’s articles everyday along with a cup of coffee.
Hi Deepak,
The loop in the singly-linked list doesn’t have to be at the head. It can be like this for example… A->B->C->D->E->C
You logic won’t be able to detect the loop since it will never reach the head again. Hope this helps.
I have a question.
Why do we need to have two pointers tortoise and hare.
just have a head pointer and loop over the list and check if we get the head pointer again. This will also do in O(n) and serve the problem. I think we can compare the two pointers since it has the same memory location value in it.
Please some one let me know what is the limitation in my solution.
First algorithm is much more efficient than teleporting tortoise if you write it right. Teleporting tortoise iterates nodes more than the size n always while first algorithm never go over n.
Algorithm:
bool hasLoop( Node *startNode )
{
Node *slowNode, *fastNode;
slowNode = fastNode = startNode;
if(fastNode)
fastNode = fastNode->next;
while( slowNode && fastNode )
{
if( slowNode == fastNode)
return true;
slowNode = slowNode->next;
fastNode = fastNode->next;
if(fastNode)
fastNode = fastNode->next;
}
return false;
}
My previous comment used the “code” tag – I have no idea why it didn’t format correctly.
It’s much more efficient to use a teleporting tortoise.
bool hasLoop( Node *startNode )
{
Node *tortoise, *hare;
int test_size = 2, steps_taken = 0;
tortoise = hare = startNode;
while( tortoise && hare->next )
{
hare = hare->next, steps_taken++;
if( tortoise == hare )
{
return true;
}
if ( steps_taken>=test_size )
{
steps_taken = 0, test_size *= 2;
tortoise = hare;
}
}
return false;
}