Friday, January 22, 2021

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