Detecting a cycle in a singly linked list

Idea to detect a cycle in a singly linked list is a below.

• Traverse the linked list from the head node and store the nodes in a set as they are visited. Every time a node is visited, check if it exists in the set; if it does then a cycle is detected.

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)
{}
};

public:

{}

// Detect cycle returns a node where the cycle beings.
// If no cycle is found, a nullptr is returned.

set<Node*> set_nodes;

} else {
}
}
return nullptr;
}

std :: cout << "Freeing node in the linked list.";

set <Node *> deleted_nodes;

}
}
};

int main() {

Node *node_3 = new Node(3);
Node *node_5 = new Node(5);
Node *node_7 = new Node(7);
Node *node_13 = new Node(13);

node_3->next = node_5;
node_5->next = node_7;
node_7->next = node_13;
node_13->next = node_5;

if (tmp) {
std :: cout << "Cycle begins at node : " << tmp->data << std :: endl;
} else {
std :: cout << "No cycle detected." << std :: endl;
}

return 0;
}
``````

Output

``````Cycle begins at node : 5
Freeing node in the linked list.
``````