Detecting a Loop in a Singly Linked List
September 11, 2010 in linked list
Given a singly linked list, find if there exist a loop.
This is one of the most common interview questions asked during a technical interview. I call it the classic linked list question.
The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.
Hint: The best approach uses only O(N) time and O(1) space. Remember my previous post? Try to use two pointers to traverse the list.
Solution:
The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.
1 2 3 4 5 6 7 8 9 10 | bool hasLoop(Node *head) { Node *slow = head, *fast = head; while (slow && fast && fast->next) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; } |
This elegant algorithm is known as Floyd’s cycle finding algorithm, also called the Tortoise and hare algorithm.
Alternative solutions:
There is another alternative solution that also runs in O(N) time and O(1) space, but the catch is it requires modification to the list. Try reversing the list if it has a loop in it. What do you see? Yes, eventually you will arrive back at the beginning (the head node). Read my post here on how to reverse a linked list iteratively and recursively.
More linked list practice:
If you are kind of rusty on pointers, solving all kinds of linked list problems are good exercises.
Here are some very common questions on linked list from easy to difficult, all available for download in a single pdf file. Highly recommended!
Detecting a Loop in a Singly Linked List,
Vamsi said on February 24, 2011
Here is the little improvement I see.
Line 3 can be while( fast && fast->next) don’t need to check for slow.
Greed said on May 25, 2011
Would you please write a post on fixing the loop in the list ?
Onik said on May 27, 2011
you need to check whether fast->next==slow
because fast might skip slow since it is taking two steps at a time
yc said on August 7, 2012
Is there a way to find out the starting point of the loop if there is a loop in the link list?
michael said on October 23, 2012
@yc, once slow pointer meets the fast pointer start another one step slow pointer at the start of the list. one step for both slow pointers, they will meet at the starting pointer of the loop.