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.
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
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
package com.journaldev.linkedlist.reverse; /** * A very simple linked list implementation * Not to use in application, created to show the linked list * operations, hence very minimal features * * @author pankaj * */ public class MyLinkedList { public Node head; public static class Node { public Node next; public Object data; public Node(Object data) { this.data = data; next = null; } } } |
The following class contains the method to detect a loop in the LinkedList.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
package com.journaldev.linkedlist.loopDetection; import com.journaldev.linkedlist.reverse.MyLinkedList; import com.journaldev.linkedlist.reverse.MyLinkedList.Node; public class DetectLinkedListLoop { public static void main(String[] args) { MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.head = new Node(1); myLinkedList.head.next = new Node(2); Node node = myLinkedList.head.next.next = new Node(3); myLinkedList.head.next.next.next = new Node(4); myLinkedList.head.next.next.next.next = new Node(5); myLinkedList.head.next.next.next.next.next = node; System.out.println("Has Loop? " + hasLoop(myLinkedList)); } private static boolean hasLoop(MyLinkedList myLinkedList) { Node head = myLinkedList.head; Node slow = head; Node fast = head; boolean loop = false; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { loop = true; break; } } return loop; } } |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
private static Node startNode(MyLinkedList myLinkedList) { Node head = myLinkedList.head; Node slow = head; Node fast = head; boolean loop = false; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { loop = true; break; } } if (loop) { slow = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } else { return new Node(Integer.MIN_VALUE); } } |
Call the above method in the main:
|
1 2 3 |
System.out.println("Start Node data: " + startNode(myLinkedList).data); |
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
private static int lengthOfLoop(MyLinkedList myLinkedList) { Node head = myLinkedList.head; Node slow = head; Node fast = head; boolean loop = false; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { loop = true; break; } } if (loop) { int length = 0; slow = head; while (fast != slow) { fast = fast.next; slow = slow.next; } do { fast = fast.next; length++; } while (fast != slow); return length; } return 0; } |
Call the above method in the main:
|
1 2 3 |
System.out.println("Length of loop: " + lengthOfLoop(myLinkedList)); |
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:
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.|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
private static Node removeLoop(MyLinkedList myLinkedList) { Node head = myLinkedList.head; Node slow = head; Node fast = head; boolean loop = false; while (slow != null && fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { loop = true; break; } } if (loop) { slow = head; while (fast != slow) { fast = fast.next; slow = slow.next; } while (fast.next != slow) { fast = fast.next; } fast.next = null; return head; } return head; } |
Call the above method in the main:
|
1 2 3 4 |
myLinkedList.head = removeLoop(myLinkedList); System.out.println("Has Loop? " + hasLoop(myLinkedList)); |
The complete output is:
Floyd’s Cycle-Finding Algorithm
Time Complexity: O(n)
Auxiliary Space: O(1)
That brings an end to this tutorial.