Floyd’s Cycle Detection Algorithm or the Hare-Tortoise Algorithm is a two pointer approach based algorithm. It is most commonly used in finding loop in a linked list, but it can also be used in solving the problems where we are required to find the number which is repeating in an array of N numbers, in O(N) time complexity.
It uses two pointers, out of which, one is slow, which moves 1 position, and the other is fast, which moves 2 positions at a time.
How does Floyd’s Cycle Detection Algorithm Works?
While traversing the linked list one of these things will occur:
- The Fast pointer may reach the end (null) this shows that there is no loop n the linked list.
- The Fast pointer again catches the slow pointer at some time during the iteration, therefore a loop exists in the linked list (or an array).
Pseudocode:
- Initialize two-pointers and start traversing the linked list.
- Move the slow pointer by one position.
- Move the fast pointer by two positions.
- If both pointers meet at some point then a loop exists and if the fast pointer meets the end (null) position then no loop exists.
Below is the implementation for the Floyd’s Cycle Detection Algorithm:
In C++:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
// initialize a new head for the linked list
Node* head = NULL;
class Linkedlist {
public:
// insert new value at the start
void insert(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
head = newNode;
else {
newNode->next = head;
head = newNode;
}
}
// detect if there is a loop
// in the linked list
bool detectLoop()
{
Node *slowPointer = head,
*fastPointer = head;
while (slowPointer != NULL
&& fastPointer != NULL
&& fastPointer->next != NULL) {
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;
if (slowPointer == fastPointer)
return 1;
}
return 0;
}
};
int main()
{
Linkedlist l1;
// inserting new values
l1.insert(10);
l1.insert(20);
l1.insert(30);
l1.insert(40);
l1.insert(50);
// adding a loop for the sake
// of this example
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = head;
// loop added;
if (l1.detectLoop())
cout << "Loop exists in the"
<< " Linked List" << endl;
else
cout << "Loop does not exists "
<< "in the Linked List" << endl;
return 0;
}
Output
Loop exists in the Linked List
In Java:
import java.util.*;
class Solution{
static class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
};
static Node head = null;
static class Linkedlist {
void insert(int value)
{
Node newNode = new Node(value);
if (head == null)
head = newNode;
else {
newNode.next = head;
head = newNode;
}
}
boolean detectLoop()
{
Node slowPointer = head,
fastPointer = head;
while (slowPointer != null
&& fastPointer != null
&& fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if (slowPointer == fastPointer)
return true;
}
return false;
}
}
public static void main(String[] args)
{
Linkedlist l1 = new Linkedlist();
// inserting new values
l1.insert(10);
l1.insert(20);
l1.insert(30);
l1.insert(40);
l1.insert(50);
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = head;
// loop added;
if (l1.detectLoop())
System.out.print("Loop exists in the"
+ " Linked List" +"\n");
else
System.out.print("Loop does not exists "
+ "in the Linked List" +"\n");
}
}
Output
Loop exists in the Linked List
Time Complexity is O(N) as we have traversed the list only once. The space complexity is O(1), i.e., constant space is used to initialize two pointers.
We have a mathematical proof for, why does Floyd’s Cycle Detection Algorithm works. We won’t go that way for proving that. You can check out this if you are interested.
Mathematical proof of Floyd’s Cycle Detection Algorithm
Some problems also require us to determine the point where the cycle starts in a linked list.
We need to reset the slow pointer to the head (or starting point of the linked list) and again move the slow and fast pointer, but, this time, 1 position at a time for slow as well as fast pointer.
If you have read the mathematical proof given in the link above, you might have observed that they both will meet again at a point which is the starting point of the cycle.
Below is the implementation for the same:
In C++:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};
Node* head = NULL;
class Linkedlist {
public:
// insert new value at the start
void insert(int value)
{
Node* newNode = new Node(value);
if (head == NULL)
head = newNode;
else {
newNode->next = head;
head = newNode;
}
}
// detect if there is a loop
// in the linked list
Node* detectLoop()
{
Node *slowPointer = head,
*fastPointer = head;
while (slowPointer != NULL
&& fastPointer != NULL
&& fastPointer->next != NULL) {
slowPointer = slowPointer->next;
fastPointer = fastPointer->next->next;
if (slowPointer == fastPointer)
break;
}
// if no loop exists
if (slowPointer != fastPointer)
return NULL;
// reset slow pointer to head
// and traverse again
slowPointer = head;
while (slowPointer != fastPointer) {
slowPointer = slowPointer->next;
fastPointer = fastPointer->next;
}
return slowPointer;
}
};
int main()
{
Linkedlist l1;
// inserting new values
l1.insert(10);
l1.insert(20);
l1.insert(30);
l1.insert(40);
l1.insert(50);
Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
// loop added;
temp->next = head;
Node* loopStart = l1.detectLoop();
if (loopStart == NULL)
cout << "Loop does not exists" << endl;
else {
cout << "Loop does exists and starts from "
<< loopStart->data << endl;
}
return 0;
}
Output
Loop does exists and starts from 50
In Java:
import java.util.*;
public class Solution{
static class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
static Node head = null;
static class Linkedlist {
void insert(int value)
{
Node newNode = new Node(value);
if (head == null)
head = newNode;
else {
newNode.next = head;
head = newNode;
}
}
// detect if there is a loop
// in the linked list
public Node detectLoop()
{
Node slowPointer = head,
fastPointer = head;
while (slowPointer != null
&& fastPointer != null
&& fastPointer.next != null) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next.next;
if (slowPointer == fastPointer)
break;
}
// if no loop exists
if (slowPointer != fastPointer)
return null;
// reset slow pointer to head
// and traverse again
slowPointer = head;
while (slowPointer != fastPointer) {
slowPointer = slowPointer.next;
fastPointer = fastPointer.next;
}
return slowPointer;
}
}
public static void main(String[] args)
{
Linkedlist l1 = new Linkedlist();
// inserting new values
l1.insert(10);
l1.insert(20);
l1.insert(30);
l1.insert(40);
l1.insert(50);
// adding a loop for the sake
// of this example
Node temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = head;
// loop added;
Node loopStart = l1.detectLoop();
if (loopStart == null)
System.out.println("Loop does not exists" );
else {
System.out.println("Loop does exists and starts from "
+ loopStart.data);
}
}
}Output
Loop does exists and starts from 50
That’s all for the linked list but how to solve the problems like,
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, and we have to find that repeated number.
We are also given with the instruction that we must solve the problem without modifying the array nums and uses only constant extra space.
Here comes the Floyd’s Cycle Detection Algorithm handy.
Here’s a pseudo code for this problem:
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
fast,slow=0,0
while True:
slow=nums[slow]
fast=nums[nums[fast]]
if slow==fast:
break
slow2=0
while True:
slow=nums[slow]
slow2=nums[slow2]
if slow==slow2:
return slow- This problem states that we have to find the duplicate number in the list without using extra space but we are given that there are numbers ranging from [1,n] and there are n+1 number in the list ,We could actually use this fact as an advantage.
- So first we have to know this can be seen as a linked list problem where each number in a list is the pointer to the next one. This can be seen in below illustration
index=[0,1,2,3,4]
nums=[1,3,4,2,2]
* You could see that the first element in the list is 1 which means the next element will be at index 1 which is 3 .Now the number is 3 and so the next number will be at index 3 which is number 2,now we will see index 2 which is a 4 and at index 4 there is 2 and now we see that there are two ways to go to index 2 one is from index 3 and other is at index 4.