DAA: Floyd Cycle Detection

Floyd Cycle Detection

Floyd Cycle algorithm is one of the cycle detection algorithms to detect the cycle in a given singly linked list.

In the Floyd Cycle algorithm, we have two pointers that initially point at the head. The idea of this algorithm is based on Hare and Tortoise story.

In Hare and Tortoise’s story, Hare moves twice as fast as Tortoise, and whenever the hare reaches the end of the path, the tortoise reaches the middle of the track.

Idea behind the approach -

?      Keep the Hare and Tortoise at the head node of the List.

?      In start hare moves twice as fast as tortoise.

?      While moving if hare reaches the end of the link list there is no cycle present.

?      Else move Hare and Tortoise one step ahead.

?      While moving if hare and tortoise reach same node then we get a loop.

?     Else start with step 2.

Note: Here in the code implementation, the hare is the fast pointer in our LinkedList, and the tortoise is the slow pointer in the LinkedList.

C++ code:

 #include<bits/stdc++.h>
 using namespace std;
 // Structure of Linked List nodes
 struct Node
 {
     int data;
     Node* next;
 };
 Node *head = NULL;
 void insert(int value)
 {
     // Create a new node and adjusting links
     Node* temp = new Node;
     temp->data = value;
     temp->next = head;
     head = temp;
 }
  // Function to detect cycle
 bool detectCycle()
 {
     Node *slow_ptr = head;
     Node *fast_ptr = head;  
     while (fast_ptr && fast_ptr->next)
     {
         slow_ptr = slow_ptr->next;
         fast_ptr = fast_ptr->next->next;
         if (slow_ptr == fast_ptr)
            return true; // In case if cycle is present
     }
     return false; // No cycle present
 }
 // Main Method to implement Floyd cycle algorithm
 int main()
 {
     int values[]={20, 30, 40, 50, 60};
     int n=sizeof(values)/sizeof(values[0]);
     for(int i= n-1; i>=0 ;i--)
         insert(values[i]);
     // Creating a loop
     head->next->next->next->next = head->next;
     if(detectCycle())
           cout<<"Cycle found"<<endl;
     else
           cout<<"No cycle found"<<endl; 
     return 0;
 } 

C code:

 // Floyd's Cycle Detection Algorithm
 #include <stdio.h>
 #include <stdlib.h>
 // Structure to declare a new Linked List node
 typedef struct node {
     int data;
     struct node* next;
 } node;
 node* head = NULL; // Currently head points to NULL
 // Inserting a new node into the Linked List
 node* inserting_a_new_node(int data)
 {
     node* temp;
     temp = (node*)malloc(sizeof(node));
     temp->data = data;
     temp->next = head;
     head = temp;
     return head;
 }
 // Detect if a cycle is found
 int CycleDetection(node* head)
 {
     node *pointer_fast = head, *pointer_slow = head;
     while (pointer_fast && pointer_fast->next && pointer_slow) {
         pointer_slow = pointer_slow->next;
         pointer_fast = pointer_fast->next->next;
         if (pointer_slow == pointer_fast)
             return 1;
     }
     return 0;
 }
 // Using the main method
 int main()
 {
     int n = 5;
     int linkedList[50] = { 20, 30, 40, 50, 60 };
     for (int i = 0; i < n; i++) {
         head = inserting_a_new_node(linkedList[i]);
     }
     // We are manually creating a loop
     head->next->next->next = head->next;
     if (CycleDetection(head))
         printf("Cycle is found!\n");
     else
         printf("Cycle is not found\n");
     return 0;
 } 

Java code:

 class LinkedList {
     Node head = null;
     // Linked list Node
     class Node {
         int data;
         Node next;
         Node(int val)
         {
             data = val;
             next = null;
         }
     }
     // Function to insert a node in Linked List
     public void
     insert(int val)
     {
         Node temp = new Node(val);
         temp.next = head;
         head = temp;
     }
     // Function to detect a cycle in Linked List
     boolean detectCycle()
     {
         Node slow_ptr = head;
         Node fast_ptr = head;
         while (fast_ptr != null && fast_ptr.next != null) {
             slow_ptr = slow_ptr.next;
             fast_ptr = fast_ptr.next.next;
             if (slow_ptr == fast_ptr) {
                 return true;
             }
         }
         return false;
     }
     // Main method
 public
     static void main(String args[])
     {
         LinkedList list = new LinkedList();
         int values[] = { 10, 20, 30, 40 };
         int n = values.length;
         for (int i = n - 1; i >= 0; i--)
             list.insert(values[i]);
         // Creating a loop
         list.head.next.next.next.next = list.head.next;
         if (list.detectCycle())
             System.out.println("Cycle found");
         else
             System.out.println("No cycle found");
     }
 } 

Python code:

 class Node:
     def __init__(self, data):
         self.data = data
         self.next = None
 class LinkedList:
     def __init__(self):
         self.head = None
     def insert(self, val):
         temp = Node(val)
         temp.next = self.head
         self.head = temp
 #Function to detect cycle in Linked List 
     def detectCycle(self):
         slow_ptr = self.head
         fast_ptr = self.head
         while(fast_ptr and fast_ptr.next):
             slow_ptr = slow_ptr.next
             fast_ptr = fast_ptr.next.next
             if slow_ptr == fast_ptr:
                 return True
         return False
 #Driver Code
 mylist = LinkedList()
 values=[20, 30, 40, 50, 60]
 n= len(values)
 for i in range(n-1,-1,-1):
     mylist.insert(values[i])
 #Creating a loop in Linked List
 mylist.head.next.next.next.next = mylist.head.next
 if mylist.detectCycle():
     print("Cycle found")
 else:
     print("No cycle found") 

Output:

Cycle Found