Detecting a Loop in a Singly 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.

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!

» Linked List Problems

VN:F [1.9.22_1171]
Rating: 4.8/5 (14 votes cast)
Detecting a Loop in a Singly Linked List, 4.8 out of 5 based on 14 ratings

15 thoughts on “Detecting a Loop in a Singly Linked List

  1. Onik

    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
    1. Brady Fang

      VA:F [1.9.22_1171]
      +2
      1. cj

        void 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;
        }

        VA:F [1.9.22_1171]
        0
  2. michael

    @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]
    +2
  3. Like Zhou

    O(n) and no extra space:

    VN:F [1.9.22_1171]
    +1
  4. jiya

    we 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?

    VA:F [1.9.22_1171]
    -1

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*