Detect a cycle in Linked List
Detecting a loop or cycle in linked list is a very common questions asked in the interview.Generally , several methods/approaches are questioned about solving this question. This question involves a major algorithm which is very useful in detecting cycles like in graphs and linked list. .
A cycle in graph makes it Acyclic where as in linked list it’s points to the same address in memory.
Prequesite: Singly Linked List
The cycle in linked list can be detect by using Hashing and Floyd’s cyclefinding Algorithm.
Basic Approach :
We need to make changes to the structure of the Linked list.
 Have a visited Flag with each linked list
 Traverse the coupled list and keep marking visited nodes.
 If you see a visited node more than once , then there is a loop.
Now, the loop is detected but the problem is that it needs a extra data with every node which increases space complexity to O(n), where ‘n’ is number of nodes.
Structure of the node looks like :
Struct node { int data; int flag; Struct node *next; }
Hashing :
 Linearly traversing the link list node by node till the end of the list .
 Storing the address of each in hash table with the information on link list as key value and address as index value.
 If hash has duplicate entry , then we can say that the linked list has loop in it .
The time complexity of the approach is O(N) , where ‘N’ is the size of the linked list.
Also, it makes a copy of the link list in Hash table , so it consumes a O(N) space.
Using Floyd’s cyclefinding Algorithm:
This Algorithm maintains two pointers ,let say ptr1 and ptr2 .
The first pointer ptr1 is incremented by 1 unit and the other pointer is incremented by 2 unit.
The “Tortoise and Hare Algorithm” is another name for the Algorithm. At each step , the tortoise is moved by one step and hare is moved by two steps. The point at which both the tortoise and hare have same values is declared to form a cycle.
Basically this algorithm is used to detect cycles in the directed Graph.
Let us consider the situation of cycle in linked list.

We initially mark the two pointer , ptr1 and ptr2 pointing to the head of link list.

Traversing the link list with the three conditions in the while loop

Ptr1 upto null

Ptr2 upto null

Ptr2>next utpo null

Each time it comes outside the while loop , ptr1 is incremented by 1 unit and ptr2 is incremented by 2 unit.

And if, ptr1==ptr2 , the cycle is detected.
#include <stdio.h> #include <stdlib.h> struct Node { int info; //variable to store data struct Node* next; // next pointer }; //function to detect cycle int cycle_detect(struct Node* head) { struct Node* ptr1 = head, *ptr2=head; //two pointers ptr1 and ptr2 while (ptr1 && ptr2 && ptr2>next) // run loop till these 3 conditions { ptr1=ptr1>next; //increment ptr1 by 1 unit ptr2=ptr2>next>next; //ptr2 by 2 unit //when ptr1 and ptr2 point to same node if(ptr1==ptr2){ printf("A cycle is detected at %d", ptr1>info); return 1; } } return 0; } void addtobeg(struct Node** head, int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode>info = data; newNode>next = *head; *head = newNode; } int main() { int ar[] = { 5, 10, 4, 2, 1}; int n = sizeof(ar)/sizeof(ar[0]); struct Node* head = NULL; for (int i = n  1; i >=0; i) addtobeg(&head, ar[i]); head>next>next>next=head; cycle_detect(head); return 0; }
Comments
No comment yet.