Data Structure Linked List: Detect and Remove Loop in a Linked List

 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 #include <queue>
 5 #include <stack>
 6 #include <string>
 7 #include <fstream>
 8 #include <map>
 9 #include <set>
10 using namespace std;
11 
12 struct node {
13     int data;
14     node *next;
15     node() : data(0), next(NULL) { }
16     node(int d) : data(d), next(NULL) { }
17 };
18 
19 void push(node* &head, int k) {
20     node *new_node = new node(k);
21     new_node->next = head;
22     head = new_node;
23 }
24 
25 void detectandremove(node *&head) {
26     node *p, *q;
27     p = q = head;
28     while (q && q->next) {
29         q = q->next->next;
30         p = p->next;
31         if (p == q) break;
32     }
33     if (!q || !q->next) return; //no loop
34     q = head;
35     while (q != p) {
36         q = q->next;
37         p = p->next;
38     } //get the starting point of the ring
39     while (q->next != p) q = q->next; //get the point before the starting point of the ring
40     q->next = NULL; //remove the ring
41 }
42 
43 void print(node *head) {
44     while (head) {
45         cout << head->data << " ";
46         head = head->next;
47     }
48 }
49 
50 int main() {
51     node *head = NULL;
52     push(head, 10);
53     push(head, 4);
54     push(head, 15);
55     push(head, 20);
56     push(head, 50);
57     push(head, 60);
58     head->next->next->next->next->next->next = head->next->next->next;
59     detectandremove(head);
60     print(head);
61     return 0;
62 }