FLOYD CYCLE FINDING ALGO for loop detection in linked list
//FLOYD CYCLE FINDING ALGO
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//create node with class
class node{
public: int data;
node* next;
};
//create funtion to push data later
void push(node** head_ref, int new_data)
{
node* new_node= new node();
new_node->data= new_data;
new_node->next= (*head_ref);
(*head_ref)= new_node;
}// push ends
//main algo
int detloop(node* list)
{
node* slow_p= list, *fast_p= list;
while(slow_p && fast_p && fast_p->next)
{
slow_p=slow_p->next;
fast_p=fast_p->next->next;
if(slow_p==fast_p) {return 1;}
}// while ends
return 0;
} //intends
int main() {
node* head= NULL;
push(&head, 20);
push(&head, 4) ;
push(&head, 15);
push(&head, 10);
//create a loop for testing
head->next->next->next->next= head;
if(detloop(head)) cout<<"loop found";
else cout<<"no loop";
return 0;
}
0 Comments:
Post a Comment
Subscribe to Post Comments [Atom]
<< Home