In this tutorial, we’ll be discussing a very popular algorithm which is used to detect whether a LinkedList has loops. It’s called Floyd’s Cycle-Finding Algorithm.

LinkedList Loop Detection

A loop exists in a LinkedList when no NULL is reached as we traverse throughout the LinkedList.

So in order to detect whether a LinkedList has a loop or not, we can traverse through the LinkedList and add each Node to the HashSet of visited notes if it’s been visited for the first item.
Once we reach a node that’s already present in the HashSet we can tell that there was a loop.

But this approach, though simpler takes up extra space.

Another way is to set a flag for the visited nodes in the LinkedList Node data itself. But again, this approach would take some additional space. More than what we used earlier.

linkedlist-loop-detect (1)

Hence, the ideal approach to detect a loop is using Floyd’s Cycle-Finding Algorithm

Floyd’s Cycle-Finding Algorithm

Floyd’s Cycle-Finding Algorithm uses two pointers that move at different speeds. If there is a cycle, both of the pointers would point to the same value at some point in the future.

Floyd’s Cycle-Finding Algorithm is similar to the Tortoise Hair Story.

Let’s write the Java Program to create our own LinkedList class.

MyLinkedList.java

The following class contains the method to detect a loop in the LinkedList.

We’ve moved the fast pointer at twice the speed of the slow pointer.
If there is a loop, at some point the fast and slow pointer would meet. Here we can end the while statement and return the boolean flag.

The above code returns a true.

Detect First Element of the Loop

In order to detect the starting node of the Loop, we need to add another step to the above Algorithm.

Once the fast and slow pointers are equal. Set one of them back to the start of the LinkedList head.
Move both the pointers at equal speed. At the node where they meet again, would be the starting node of the loop.

Call the above method in the main:

This will return the Node with the data 3.

Length of Loop

Once we’ve found the starting point of the loop, we can keep a pointer there and traverse the other pointer through the nodes while incrementing the length by 1.

Call the above method in the main:

The length of the loop in the above example is 3.

Removing the Loop

In order to remove the loop, we need to add another step to the above example:

Once the slow and fast pointers are at the starting node of the loop,
Traverse the fast pointer by one until its next pointer is equal to slow.That fast pointer’s current position would be the last node of the loop. We need to set the next of that node as null.

Call the above method in the main:

The complete output is:

linkedlist-loop-detect (1)

Floyd’s Cycle-Finding Algorithm

Time Complexity: O(n)
Auxiliary Space: O(1)

That brings an end to this tutorial.

You can checkout complete code and more DS & Algorithm examples from our GitHub Repository.

By admin

Leave a Reply