#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;
}