fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. class node{
  5. 	public:
  6. 	int data;
  7. 	node *next;
  8.  
  9. };
  10.  
  11. void print(node *p){
  12. 	while(p!=NULL){
  13. 		cout<<p->data<<"  ";
  14. 		p=p->next;
  15.  
  16. 	}
  17. 	cout<<endl;
  18. }
  19.  
  20. void removeLoop(node* loop,node* head){
  21.  
  22. 	node* ptr1=loop;
  23. 	node* ptr2=loop;
  24.  
  25. 	int k=1;
  26. 	while(ptr1->next!=ptr2){
  27. 		k++;
  28. 		ptr1= ptr1->next;
  29. 	}
  30.  
  31. 	ptr1=head;
  32. 	ptr2=head;
  33.  
  34. 	for(int i=0;i<k;i++){
  35. 		ptr1=ptr1->next;
  36. 	}
  37.  
  38. 	while(ptr1!=ptr2){
  39. 		ptr2=ptr2->next;
  40. 		ptr1=ptr1->next;
  41. 	}
  42.  
  43. 	while(ptr1->next!=ptr2)
  44. 	    ptr1=ptr1->next;
  45.  
  46. 	ptr1->next=NULL;
  47.  
  48. }
  49.  
  50. int check(node* h1){
  51.  
  52. 	node* slow ,*fast;
  53. 	slow=h1;
  54. 	fast=h1;
  55.  
  56. 	while(slow && fast && fast->next){
  57.  
  58. 		slow=slow->next;
  59. 		fast = fast->next->next;
  60.  
  61. 		if(slow == fast){
  62. 			removeLoop(slow,h1);
  63. 			return 1;
  64. 		}
  65.  
  66.  
  67. 	}
  68. 	return 0;
  69. }
  70.  
  71. int main() {
  72.  
  73.     node* head = NULL;
  74.     node* second = NULL;
  75.     node* third = NULL;
  76.  
  77.     // allocate 3 nodes in the heap
  78.     head = new node();
  79.     second = new node();
  80.     third = new node();
  81.  
  82.     head->data = 1; // assign data in first node
  83.     head->next = second; // Link first node with second
  84.  
  85.     second->data = 2; // assign data to second node
  86.     second->next = third;
  87.  
  88.     third->data = 3; // assign data to third node
  89.     third->next = head;
  90.  
  91.     if(check(head))
  92.     	print(head);
  93.  
  94. 	return 0;
  95. }
Success #stdin #stdout 0s 5592KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1  2  3
https://ideone.com/OjlOwz
detecting and removing loop in LL in less space
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!