(52). 22.5 Detection and Romoval of Cycle in Linked List. - anishsingh90/Data_Structure_And_Algorithm_In_Cpp_github.io GitHub Wiki

//DETECT CYCLE #include <bits/stdc++.h> using namespace std;

class node{ public: int data; node* next;

	node(int val){
	data = val;
	next = NULL;
	}		

};

void insertAtTail(node* &head, int val){ node* n = new node(val); if(head==NULL){ head = n; return; } node* temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = n; }

void display(node* head){ node* temp = head; while(temp != NULL){ cout << temp->data <<"->"; temp = temp->next; } cout <<"NULL"<<endl; }

//make cycle void makeCycle(node* &head, int pos){

node* temp = head; node* startNode;

int count = 1; while(temp->next != NULL){ if(count == pos){ startNode = temp; } temp = temp->next; count++; }

temp -> next = startNode;

}

bool detectCycle(node* &head){ node* slow = head; node* fast = head;

while(fast != NULL && fast -> next != NULL){
	slow = slow -> next;
	fast = fast -> next -> next;
	
if(fast==slow){
	return true;
 }

} return false; }

int main(){ node* head = NULL; insertAtTail(head,1); insertAtTail(head,2); insertAtTail(head,3); insertAtTail(head,4); insertAtTail(head,5); insertAtTail(head,6); makeCycle(head,3); // display(head);

cout << detectCycle(head) << endl;

return 0;

}

/* OUTPUT: 1 = TRUE; */

//REMOVE CYCLE #include <bits/stdc++.h> using namespace std;

class node{ public: int data; node* next;

	node(int val){
	data = val;
	next = NULL;
	}		

};

void insertAtTail(node* &head, int val){ node* n = new node(val); if(head==NULL){ head = n; return; } node* temp = head; while(temp->next != NULL){ temp = temp->next; } temp->next = n; }

void display(node* head){ node* temp = head; while(temp != NULL){ cout << temp->data <<"->"; temp = temp->next; } cout <<"NULL"<<endl; }

//make cycle void makeCycle(node* &head, int pos){

node* temp = head; node* startNode;

int count = 1; while(temp->next != NULL){ if(count == pos){ startNode = temp; } temp = temp->next; count++; }

temp -> next = startNode;

}

bool detectCycle(node* &head){ node* slow = head; node* fast = head;

while(fast != NULL && fast -> next != NULL){
	slow = slow -> next;
	fast = fast -> next -> next;
	
if(fast==slow){
	return true;
 }

} return false; }

void removeCycle(node* &head){ node* slow = head; node* fast = head;

do{
	slow = slow -> next;
	fast = fast -> next -> next;
}while(slow != fast);

fast = head;
while(slow -> next != fast -> next){
	slow = slow -> next;
	fast = fast -> next;
}

slow -> next = NULL;

}

int main(){ node* head = NULL; insertAtTail(head,1); insertAtTail(head,2); insertAtTail(head,3); insertAtTail(head,4); insertAtTail(head,5); insertAtTail(head,6); makeCycle(head,3);

cout << "After Removal Cycle: "; cout << detectCycle(head) << endl;

 cout << "Before Removal Cycle: ";
removeCycle(head);
cout << detectCycle(head) << endl;
display(head);

return 0;

}

/* OUTPUT: After Removal Cycle: 1 (Cycle is Present) Before Removal Cycle: 0 (Cycle is remove) 1->2->3->4->5->6->NULL */