Detect Loop in a Linked List

In this class, we discuss Detect Loop in a Linked List.

The reader can take a complete competitive coding course. Click Here.

Question:

Given a singly linked list.

Our task is to detect a loop in a given linked list.

Example:

Input: 1-2-3-4-5-pointing to node 3

Output: Yes

The last node points to the third node.

It is forming a loop, so the output is Yes.

Example 2:

Input: 1-2-3-None

Output: No

Time complexity: O(N)

Space complexity: O(1)

Logic:

Maintain a list of all visited nodes.

Loop on the linked list, and each node visited is maintained in a list.

Suppose we visit the node already in the list. Loop exists.

If we find None in the list, there is no loop.

Second Way:

Floyd’s cycle finding algorithm.

Two objects are moving in a circle.

One object is moving slowly, and the other object is moving fast.

The faster object will move fast and meet the slower object.

We use the same concept in finding the loop.

Take two-pointers, Slow pointers and Fast pointer.

The slow pointer moves one step, and the fast pointer moves two steps.

If there is a loop in the linked list, the fast pointer will meet the slow pointer.

Then we say the loop exists in the linked list.

Code:

def detectLoop(self, head)

        slow_p = head

        fast_p = head

        while(slow_p and fast_p and fast_p.next):

            slow_p = slow_p.next

            fast_p = fast_p.next.next

            if slow_p == fast_p:

                return True        

return False