How to detect a cycle in a linked list ?
- A linked list is said to contain a cycle if any node is visited more than once.
![How do you detect a cycle in a linked list](https://cdn.wikitechy.com/interview-questions/data-structure/how-to-detect-a-cycle-in-a-linked-list.png)
Method 1 – Using Hashing
- Traverse the given list.
- Insert each encountered node into a hash table.
- If the current already present ,that means the cycle is present or not.
Sample code
#include <iostream>
#include <unordered_set>
using namespace std;
// Data Structure to store a linked list node
struct Node
{
int dt;
Node* next;
};
// Helper function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int dt)
{
// create a new linked list node from heap
Node* newNode = new Node;
newNode->dt = dt;
newNode->next = headRef;
headRef = newNode;
}
// Function to detect Cycle in a linked list using Hashing
bool detectcyc(Node *head)
{
Node *current = head;
unordered_set<Node*> set;
// traverse the list
while (current)
{
// return false if we already have seen this node before
if (set.find(current) != set.end())
return true;
// insert current node into the set
set.insert(current);
// move to the next node
current = current->next;
}
// we reach here if list does not contain any cycle
return false;
}
// Detect Cycle in a linked list
int main()
{
// input keys
int k[] = { 1, 2, 3, 4, 5 };
int n = sizeof(k) / sizeof(k[0]);
Node* head = nullptr;
for (int i = n - 1; i >= 0; i--)
push(head, k[i]);
// insert cycle
head->next->next->next->next->next = head->next->next;
if (detectcyc(head))
cout << "Cycle Found";
else
cout << "No Cycle Found";
return 0;
}
Output
Cycle Found
Method 2 – Floyd’s Cycle Detection Algorithm
- Use two pointers, which move through the sequence at different speed.
- The fast pointer moves twice as quickly as the slow pointer.
- Here the distance between the two pointers increased by 1 at each step.
- If these pointers meet at same node then there is a loop else linked list doesn’t have loop.
Sample Code
#include <iostream>
#include <unordered_set>
using namespace std;
// Data Structure to store a linked list node
struct Node
{
int dt;
Node* next;
};
// Helper function to create a new node with the given data and
// pushes it onto the front of the list
void push(Node*& headRef, int dt)
{
// create a new linked list node from heap
Node* nNode = new Node;
nNode->dt = dt;
nNode->next = headRef;
headRef = nNode;
}
// Function to detect Cycle in a linked list using
// Floyd’s Cycle Detection Algorithm
bool dcycle(Node *head)
{
// take two pointers - slow and fast
Node *slow = head, *fast = head;
while (fast && fast->next)
{
// move slow by one pointer
slow = slow->next;
// move fast by two pointers
fast = fast->next->next;
// if they meet any any node, linked list contains a cycle
if (slow == fast)
return true;
}
// we reach here if slow & fast pointer do not meet
return false;
}
// Detect Cycle in a linked list using Floyd’s Cycle Detection Algorithm
int main()
{
// input keys
int k[] = { 1, 2, 3, 4, 5 };
int n = sizeof(k) / sizeof(k[0]);
Node* head = nullptr;
for (int i = n - 1; i >= 0; i--)
push(head, k[i]);
// insert cycle
head->next->next->next->next->next = head->next->next;
if (dcycle(head))
cout << "Cycle Found";
else
cout << "No Cycle Found";
return 0;
}
Output
Cycle Found
Categorized in:
Tagged in:
Accenture interview questions and answers, Altimetrik India Pvt Ltd interview questions and answers, Applied Materials interview questions and answers, Bharti Airtel interview questions and answers, BMC Software interview questions and answers, Capgemini interview questions and answers, CASTING NETWORKS INDIA PVT LIMITED interview questions and answers, CGI Group Inc interview questions and answers, Chetu interview questions and answers, Ciena Corporation interview questions and answers, circular linked list java, Collabera Te interview questions and answers, Comodo India Interview Questions and Answers, cycle detection linked list, cycle detection solution, cycle detection solution c++, Dell International Services India Pvt Ltd interview questions and answers, find cycle in linked list, find length of loop in linked list, find loop in linked list, find start of loop in linked list, Flipkart interview questions and answers, floyd's cycle detection algorithm, floyd's cycle finding algorithm, floyd's cycle-finding algorithm c++, Genpact interview questions and answers, given a linked list, Globallogic India Pvt Ltd interview questions and answers, IBM interview questions and answers, Indecomm Global Services interview questions and answers, leetcode sort linked list, link cycle, linked list, linked list cycle, linked list in data structure, linked lists detect a cycle, list cycle, Mphasis interview questions and answers, n'th node from end of linked list, nested loops java, NetApp interview questions and answers, Oracle Corporation interview questions and answers, python linked list cycle, remove loop in linked list, return the node where the cycle begins. if there is no cycle, SAP Labs India Pvt Ltd interview questions and answers, Sapient Consulting Pvt Ltd interview questions and answers, Tech Mahindra interview questions and answers, Tracxn Technologies Pvt Ltd interview questions and answers, UnitedHealth Group interview questions and answers, what is linked list in data structure, Wipro Infotech interview questions and answers, WM Global Technology Services India Pvt.Ltd Limited (WMGTS) interview questions and answers, Xoriant Solutions Pvt Ltd interview questions and answers, Yodlee Infotech Pvt Ltd interview questions and answers