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 cycle-finding 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 cycle-finding 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.