What is Floyd’s algorithm?

Introduction

Floyd's cycle-detection algorithm is used to detect a cycle (or a loop) in the singly linked list. A linked list contains a cycle if the same node is reached by continuously following the next pointer. An example of a linked list with a cycle is given below:

Algorithm

The steps of Floyd's algorithm are shown below:

Take two pointers and label them as fast and slow.
Point out both pointers to the head of the linked list.
Move the slow pointer by one node and the fast pointer by two nodes while traversing a linked list.
The loop is detected if both pointers meet at the same node.
If both pointers do not meet at the same node and the fast pointer reaches the end of the linked list, then there is no loop in the linked list.

The demonstration below explains the process if a linked list contains a cycle:

bool Loop_Detection(Node *head) //function to detect a loop
{
	Node *slow = head ;
	Node *fast = head ;
	while (fast != NULL)
	{
		if(fast -> next != NULL)
		{
			slow = slow -> next;
			fast = fast -> next -> next ;
		} 
		else 
		{
			return 0;
		}
		if(fast == slow)
			return 1;
	}
	return 0;
}
int main()
{
	//Creating Linked list
	Node *node1 = new Node ;
	Node *node2 = new Node ;
	Node *node3 = new Node ;
	Node *node4 = new Node ;
	Node *node5 = new Node ;
	node1->data=1; node2->data=2; node3->data=3; node4->data=4; node5->data=5;
	node1 -> next = node2 ;
	node2 -> next = node3 ;
	node3 -> next = node4 ;
	node4 -> next = node5 ;
	node5 -> next = node2 ;
	//passing head of linked list
	bool is_loop = Loop_Detection(node1);
	if(is_loop)
		cout<<"Loop Detected!";
	else
		cout<<"No Loop Detected!";
	return 0;
}

Code explanation

The description of the code above is given below:

Line 1: We have a boolean function, Loop_Detection that returns 1 when the loop is detected and 0 if no loop is detected in the linked list.
Lines 3-4: We declare 2 Node* type pointers named as slow and fast. Both pointers point to the head of the linked list.
Line 5: We have a loop to traverse through the linked list.
Lines 9-10: We move the slow pointer at the pace of 1 and the fast pointer at the pace of 2.
Lines 16-17: If both pointers point at the same node, then return 1.
Lines 24-34: We create and initialize nodes in the linked list.
Line 36: We pass the linked list's head to Loop_Detection function to check for the cycle.

Time complexity

The time complexity of this algorithm is $O(n)$ , where $n$ is the number of nodes in the linked list, while space complexity is just $O(1)$ .