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.

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