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,
Here is the little improvement I see.

Line 3 can be while( fast && fast->next) don’t need to check for slow.

+12Would you please write a post on fixing the loop in the list ?

0you need to check whether fast->next==slow

because fast might skip slow since it is taking two steps at a time

0No, there is no probability for this because in the case you are talking about, the equality test will be succeeded a step before. You can trace it yourself.

0If fast->next==slow, then one more loop will make “fast” to meet “slow”, isn’t it:)?

+2Is there a way to find out the starting point of the loop if there is a loop in the link list?

+1+2void findStartNodeOfLoop(Node *head, Node **start) {

Node *slow = head;

Node *fast = head;

while (fast && fast->next) {

slow = slow->next;

fast = fast->next->next;

if (slow == fast) {

while(fast->next != slow )

fast = fast->next;

*start = fast;

return;

}

}

return;

}

0sorry, this is wrong. remove it please

0@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.

+2O(n) and no extra space:

+1Can we hash the next pointer and check if a value appears twice?

0Yes but it requires space of n and you have to check for every pointer weather its availabe in your list or not

0Create two references – slow and fast.

Start from the beginning of the list. slow hops one node while fast hops two.

If they meet, loop is found.

For explanation and code http://www.algoqueue.com/algoqueue/default/view/7405568/detect-a-loop-in-a-linked-list

0we can find the solution if we move the fast pointer 3 steps forward rather than just 2 steps,then why do we use this method only?

-1