#include<iostream>
using namespace std;
class node
{
public:
int value;
node *next;
node()
{
next =NULL;
value = 0;
}
};
class List
{
public:
List()
{
head = NULL;
}
node *head;
bool insert_node(node *p_head,int p_value)
{
node *temp= new node();
temp->next = NULL;
temp->value = p_value;
if(! p_head)
{
head = temp;
return true;
}
while(p_head->next != NULL)
{
p_head = p_head->next;
}
p_head->next = temp;
return true;
}
bool deduct_loop(node *p_head)
{
node *slow=NULL,*fast=NULL;
if(p_head)
slow = p_head->next;
int a;
a=5;
if(p_head->next)
fast = p_head->next->next;
/* Slow(Tortoise) will move one step at each loop and fast(Hare) moves two steps at each loop */
while(slow && fast && fast->next)
{
// Hare captured the tortoise. Always hare only capture the tortoise
if(slow == fast)
{
cout<<"\n Loop deducted!\n ";
return true;
}
slow=slow->next; // Move one step
fast=fast->next->next; // Move two step
}
// Reached End of Loop because Fast(Hare) is null
// If no loop then end of loop is always reached by hare
cout<<"\n Good Job! No Loop deducted!";
return false;
}
};
int main()
{
List list;
list.insert_node(list.head ,10);
list.insert_node(list.head ,20);
list.insert_node(list.head ,30);
list.insert_node(list.head ,60);
list.insert_node(list.head ,40);
cout<<"\n Demonstrating Linked list without loop";
list.deduct_loop(list.head);
cout<<"\n Demonstrating Linked list with loop";
(list.head)->next->next->next = (list.head)->next;
list.deduct_loop(list.head);
return 0;
}