## Detecting a Loop in a Singly Linked List

September 11, 2010

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.

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.

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!

VN:F [1.9.22_1171]
Rating: 5.0/5 (1 vote cast)
Detecting a Loop in a Singly Linked List, 5.0 out of 5 based on 1 rating

### 5 responses to Detecting a Loop in a Singly Linked List

1. Here is the little improvement I see.
Line 3 can be while( fast && fast->next) don’t need to check for slow.

VA:F [1.9.22_1171]
+1
2. Would you please write a post on fixing the loop in the list ?

VA:F [1.9.22_1171]
0
3. you need to check whether fast->next==slow
because fast might skip slow since it is taking two steps at a time

VA:F [1.9.22_1171]
0
4. Is there a way to find out the starting point of the loop if there is a loop in the link list?

VN:F [1.9.22_1171]
0
5. @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.

VN:F [1.9.22_1171]
0