Interview Questions
Check if linked list has a loop
Create a function which returns true or false if given linked list contains a loop.
View Solution
One way to solve it is to use hash table and to insert all nodes to hash table, if at any point we will notice that the node was previously inserted into hash table then we detected a loop. This is linear solution O(n), but also requires O(n) space.
We improve this algorithm by creating two pointers, one which will be moved to next node on every loop iteration and second one which will be moved twice as fast (two nodes forward on every iteration). If these two pointers ever meet we detected a loop, if any one of them hits null, then linked list has no loop. This solution does not require additional space and continues to have O(n) running time.
struct Node
{
Node* next;
int value;
};
Node* Move(Node* tmp, int moves)
{
while (moves-- > 0 && tmp)
{
tmp = tmp->next;
}
return tmp;
}
bool HasLoop(Node* root)
{
Node *slow = root;
Node *fast = root;
while (true)
{
slow = Move(slow, 1);
fast = Move(fast, 2);
if (!slow || !fast)
{
return false;
}
else if (slow == fast)
{
return true;
}
}
}