#include <bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node *next;
};
void print(node *p){
while(p!=NULL){
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
void removeLoop(node* loop,node* head){
node* ptr1=loop;
node* ptr2=loop;
int k=1;
while(ptr1->next!=ptr2){
k++;
ptr1= ptr1->next;
}
ptr1=head;
ptr2=head;
for(int i=0;i<k;i++){
ptr1=ptr1->next;
}
while(ptr1!=ptr2){
ptr2=ptr2->next;
ptr1=ptr1->next;
}
while(ptr1->next!=ptr2)
ptr1=ptr1->next;
ptr1->next=NULL;
}
int check(node* h1){
node* slow ,*fast;
slow=h1;
fast=h1;
while(slow && fast && fast->next){
slow=slow->next;
fast = fast->next->next;
if(slow == fast){
removeLoop(slow,h1);
return 1;
}
}
return 0;
}
int main() {
node* head = NULL;
node* second = NULL;
node* third = NULL;
// allocate 3 nodes in the heap
head = new node();
second = new node();
third = new node();
head->data = 1; // assign data in first node
head->next = second; // Link first node with second
second->data = 2; // assign data to second node
second->next = third;
third->data = 3; // assign data to third node
third->next = head;
if(check(head))
print(head);
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpjbGFzcyBub2RlewoJcHVibGljOgoJaW50IGRhdGE7Cglub2RlICpuZXh0OwogCn07Cgp2b2lkIHByaW50KG5vZGUgKnApewoJd2hpbGUocCE9TlVMTCl7CgkJY291dDw8cC0+ZGF0YTw8IiAgIjsKCQlwPXAtPm5leHQ7CiAKCX0KCWNvdXQ8PGVuZGw7Cn0KCnZvaWQgcmVtb3ZlTG9vcChub2RlKiBsb29wLG5vZGUqIGhlYWQpewoJCglub2RlKiBwdHIxPWxvb3A7Cglub2RlKiBwdHIyPWxvb3A7CgoJaW50IGs9MTsKCXdoaWxlKHB0cjEtPm5leHQhPXB0cjIpewoJCWsrKzsKCQlwdHIxPSBwdHIxLT5uZXh0OwoJfQoJCglwdHIxPWhlYWQ7CglwdHIyPWhlYWQ7CgkKCWZvcihpbnQgaT0wO2k8aztpKyspewoJCXB0cjE9cHRyMS0+bmV4dDsKCX0KCQoJd2hpbGUocHRyMSE9cHRyMil7CgkJcHRyMj1wdHIyLT5uZXh0OwoJCXB0cjE9cHRyMS0+bmV4dDsKCX0KCQoJd2hpbGUocHRyMS0+bmV4dCE9cHRyMikKCSAgICBwdHIxPXB0cjEtPm5leHQ7CgkKCXB0cjEtPm5leHQ9TlVMTDsKCQp9CgppbnQgY2hlY2sobm9kZSogaDEpewoJCglub2RlKiBzbG93ICwqZmFzdDsKCXNsb3c9aDE7CglmYXN0PWgxOwoJCgl3aGlsZShzbG93ICYmIGZhc3QgJiYgZmFzdC0+bmV4dCl7CgkJCgkJc2xvdz1zbG93LT5uZXh0OwoJCWZhc3QgPSBmYXN0LT5uZXh0LT5uZXh0OwoJCQoJCWlmKHNsb3cgPT0gZmFzdCl7CgkJCXJlbW92ZUxvb3Aoc2xvdyxoMSk7CgkJCXJldHVybiAxOwoJCX0KCQkgICAKCQkKCX0KCXJldHVybiAwOwp9CgppbnQgbWFpbigpIHsKIAogICAgbm9kZSogaGVhZCA9IE5VTEw7CiAgICBub2RlKiBzZWNvbmQgPSBOVUxMOwogICAgbm9kZSogdGhpcmQgPSBOVUxMOwogCiAgICAvLyBhbGxvY2F0ZSAzIG5vZGVzIGluIHRoZSBoZWFwCiAgICBoZWFkID0gbmV3IG5vZGUoKTsKICAgIHNlY29uZCA9IG5ldyBub2RlKCk7CiAgICB0aGlyZCA9IG5ldyBub2RlKCk7CiAKICAgIGhlYWQtPmRhdGEgPSAxOyAvLyBhc3NpZ24gZGF0YSBpbiBmaXJzdCBub2RlCiAgICBoZWFkLT5uZXh0ID0gc2Vjb25kOyAvLyBMaW5rIGZpcnN0IG5vZGUgd2l0aCBzZWNvbmQKIAogICAgc2Vjb25kLT5kYXRhID0gMjsgLy8gYXNzaWduIGRhdGEgdG8gc2Vjb25kIG5vZGUKICAgIHNlY29uZC0+bmV4dCA9IHRoaXJkOwogCiAgICB0aGlyZC0+ZGF0YSA9IDM7IC8vIGFzc2lnbiBkYXRhIHRvIHRoaXJkIG5vZGUKICAgIHRoaXJkLT5uZXh0ID0gaGVhZDsKICAgCiAgICBpZihjaGVjayhoZWFkKSkKICAgIAlwcmludChoZWFkKTsKICAgIAkKCXJldHVybiAwOwp9