How Floyd's Tortoise and the Hare Linked List Circle Detection Algorithm Works ~ Hybrid Mobile Apps Development, React Native, Flutter, JavaScript, Darts, iOS, Android, NodeJS

There are many ways of storing data when writing a computer program especially when it's a group of data that share the same property. Like the data of students under the age of 12 or People who love same category of movies. This can be store as an array or a slice into the memory but sometime you just want some that is very simple to work with when the data get massively large to go through. Cases like this are when linked list comes to play. It essentially just a sequence elements where one element links to the next element.

I won't dive deep into benefits of a linked list right now, We will leave that for another day, Rather we will look into one of the more efficient algorithm of detecting if there is a circle in any set of linked list. This algorithm is popularly know as Floyd's Circle detection algorithm and can sometimes be referred to as Tortoise and The Hare Algorithm.

The algorithm uses two pointers, The fast pointer called Hare and slow pointer called Tortoise. Hence forth I will be referring to element of a list as node. The first use-case is to find out if there is a loop in the linked list. To solve this problem we need to loop through the list and make the Hare move two nodes per iteration and the Tortoise move one node per iteration. If there is a loop the pointer are going to meet in the loop, In that case the Hare pointer will be equal to the Tortoise pointer if they are pointing at the same node. Otherwise if the Hare get to the end of the list and never point to the same node as the Tortoise then there is no loop in the list. Now that we have established that our list has a loop, The next common question is to find where the loop start. To solve this we need to know the numbers of moves the Hare and Tortoise make before they meet. Note that the part of the list that is not inside the loop is refer to as tail. The tail is amply the number of nodes before the first node in the loop.

package floyd;
private Node startNode;

public static void main(String[] args) {
DetectLoopInLinkedList detectLoopInLinkedList = new DetectLoopInLinkedList();

Node n1 = new Node(10);
Node n2 = new Node(20);
Node n3 = new Node(30);
Node n4 = new Node(40);
Node n5 = new Node(50);
Node n6 = new Node(60);
Node n7 = new Node(70);
Node n8 = new Node(80);

detectLoopInLinkedList.startNode = n1;

n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n8);
n8.setNext(n6);

if(isLoopPresent(detectLoopInLinkedList.startNode)){
System.out.println("Loop is present in list");
}else{
System.out.println("No Loop present in list");
}
}

private static boolean isLoopPresent(Node startNode){
Node slowPointer = startNode; // Initially ptr1 is at starting location.
Node fastPointer = startNode; // Initially ptr2 is at starting location.

while(fastPointer!=null && fastPointer.getNext()!=null){ // If ptr2 encounters NULL, it means there is no Loop in Linked list.
slowPointer = slowPointer.getNext(); // ptr1 moving one node at at time
fastPointer = fastPointer.getNext().getNext(); // ptr2 moving two nodes at at time

if(slowPointer==fastPointer) // if ptr1 and ptr2 meets, it means linked list contains loop.
return true;
}
return false;
}

}

public class Node{

private int data;
private Node next;

public Node(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}

Distance traveled by the slow pointer(Tortoise) before meeting =𝑥+𝑦
Distance traveled by fast fast pointer(Hare) before meeting =(𝑥+𝑦+𝑧)+𝑦 = x + 2y + z
Since fast pointer(Hare) travels double the speed of the slow pointer(Tortoise) and time is constant for both when the reach the meeting point. So by using simple speed, time and distance relation (slow pointer(Tortoise) traveled half the distance): For this case we will take distance moved by the fast pointer (Hare) as i and the distance moved by the slow pointer(Tortoise) as j.

Therefore:

2 * j = i

2(x + z) = x + 2z + (y - z)

2x + 2z = x + 2z + (y - z)

x = z

Hence by moving slow pointer(Tortoise) to starting of the linked list, and making both slow pointer and fast pointer(Hare) to move one node at a time, they both have same distance to cover. They will reach at the node where the loop starts in the list.

Was this article helpful?

☺Yes, thanks!

☹Not really

Thanks! Your feedback helps us improve tutorials.