#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
int data;
Node *next;
Node(int d)
{
data = d;
next = NULL;
}
};
// head - Head pointer of the Linked List
// Return a boolean value indicating the presence of cycle
// If the cycle is present, modify the linked list to remove the cycle as well
bool floydCycleRemoval(Node head)
{
Nodefast=head;
Node*slow=head;
fast=fast->next->next;
slow=slow->next;
while(fast!=NULL && fast->next!=NULL){
if(fast==slow){
int k=1;
slow=slow->next;
while(slow!=fast){
k++;
slow=slow->next;
}
// now point slow to head and fast to k node ahead
slow=head;
fast=head;
while(k--){
fast=fast->next;
}
/// move slow and fast one by one
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
// now move only fast
while(fast->next!=slow){
fast=fast->next;
}
fast->next=NULL;
return true;
}
fast=fast->next->next;
slow=slow->next;
}
return false;
}
void buildCycleList(Node *&head)
{
unordered_map<int, Node *> hash;
int x;
cin >> x;
if (x == -1)
{
head = NULL;
return;
}
head = new Node(x);
hash[x] = head;
Node *current = head;
while (x != -1)
{
cin >> x;
if (x == -1)
break;
if (hash.find(x) != hash.end())
{
current->next = hash[x];
return;
}
Node *n = new Node(x);
current->next = n;
current = n;
hash[x] = n;
}
current->next = NULL;
}
void printLinkedList(Node *head)
{
unordered_set s;
while (head != NULL)
{
if (s.find(head->data) != s.end())
{
cout << "\nCycle detected at " << head->data;
return;
}
cout << head->data << " ";
s.insert(head->data);
head = head->next;
}
}
int main()
{
Node *head = NULL;
buildCycleList(head);
bool cyclePresent = floydCycleRemoval(head);
if (cyclePresent)
{
cout << "Cycle was present\n";
}
else
{
cout << "No cycle\n";
}
cout << "Linked List - ";
printLinkedList(head);
return 0;
}