Idea to detect a cycle in a singly linked list is a below.
Time Complexity : O ( N ), where N is the number of nodes in the linked list. Space Complexity : O ( N ), where N is the number of nodes in the linked list.
C++ program to detect a cycle in a singly linked list.
#include<iostream>
#include<set>
using namespace std;
class Node {
public:
int data;
Node* next;
Node (int arg_data) : data (arg_data), next (nullptr)
{}
};
class SingleLinkedList {
public:
SingleLinkedList()
{}
// Detect cycle returns a node where the cycle beings.
// If no cycle is found, a nullptr is returned.
Node* Detect_Cycle (Node *head) {
set<Node*> set_nodes;
while (head != nullptr) {
if (set_nodes.find(head) == set_nodes.end()) {
set_nodes.insert(head);
head = head->next;
} else {
return head;
}
}
return nullptr;
}
// Free the linked list
void Free (Node *head) {
std :: cout << "Freeing node in the linked list.";
set <Node *> deleted_nodes;
while (head != nullptr && deleted_nodes.find(head) == deleted_nodes.end()) {
Node * temp = head->next;
head->next = nullptr;
delete head;
deleted_nodes.insert(head);
head = temp;
}
}
};
int main() {
Node *head = new Node(2);
Node *node_3 = new Node(3);
Node *node_5 = new Node(5);
Node *node_7 = new Node(7);
Node *node_13 = new Node(13);
head->next = node_3;
node_3->next = node_5;
node_5->next = node_7;
node_7->next = node_13;
node_13->next = node_5;
SingleLinkedList s;
Node * tmp = s.Detect_Cycle(head);
if (tmp) {
std :: cout << "Cycle begins at node : " << tmp->data << std :: endl;
} else {
std :: cout << "No cycle detected." << std :: endl;
}
s.Free(head);
return 0;
}
Output
Cycle begins at node : 5
Freeing node in the linked list.