#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)
{ bool flag = false;
//ok ji i am gone a do this it actually seems much easier anyway
Node fast = head;
Node* slow = head;
int answer = 0;
while(fast!=NULL || fast->next != NULL){
fast = fast->next->next;
slow = slow->next;
if(fast->next == slow->next){
flag = true;
break;
}
}
if(flag){
Node* end = head;
while(end != slow){
slow = slow->next ;
end = end->next;
}
slow = slow->next;
while(slow->next != end){
slow =slow ->next;
}
slow ->next = NULL;
}
return flag;
//now you also have to remove the this thing so called cycle
}
/*
*
*
- You do not need to refer or modify any code below this.
- Only modify the above function definition.
- Any modications to code below could lead to a ‘Wrong Answer’ verdict despite above code being correct.
- You do not even need to read or know about the code below.
*/
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;
}
