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:
Note: The linked list has no end if there is a loop in it.
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:
When the linked list does not contain a cycle, the algorithm works as shown in the illustration below:
Code
The C++ implementation of Floyd's Cycle Detection Algorithm is shown in the code widget below:
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 listNode *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 listbool is_loop = Loop_Detection(node1);if(is_loop)cout<<"Loop Detected!";elsecout<<"No Loop Detected!";return 0;}
Code explanation
The description of the code above is given below:
- Line 1: We have a boolean function,
Loop_Detectionthat returns1when the loop is detected and0if 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
1and the fast pointer at the pace of2. - 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_Detectionfunction to check for the cycle.
Time complexity
The time complexity of this algorithm is
