#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; }
Thursday, 7 August 2014
C++ program to deduct a loop in a singly linked list (Tortoise and hare method or Cycle deduction algorithm)
Posted by
VINOTH KUMAR G
at
11:38:00
No comments:
Labels:
Algorithm,
C++,
Data-structure,
Git-hub,
Sample-programs
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment