Detect loop in a linked list | C ++ program to detect loop in a linked list ; Link list node ; allocate node ; put in the data ; link the old list off the new node ; move the head to point to the new node ; Returns true if there is a loop in linked list else returns false . ; If this node is already traverse it means there is a cycle ( Because you we encountering the node for the second time ) . ; If we are seeing the node for the first time , mark its flag as 1 ; Driver program to test above function ; Start with the empty list ; Create a loop for testing
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; int flag ; } ; void push ( struct Node * * head_ref , int new_data ) { struct Node * new_node = new Node ; new_node -> data = new_data ; new_node -> flag = 0 ; new_node -> next = ( * head_ref ) ; ( * head_ref ) = new_node ; } bool detectLoop ( struct Node * h ) { while ( h != NULL ) { if ( h -> flag == 1 ) return true ; h -> flag = 1 ; h = h -> next ; } return false ; } int main ( ) { struct Node * head = NULL ; push ( & head , 20 ) ; push ( & head , 4 ) ; push ( & head , 15 ) ; push ( & head , 10 ) ; head -> next -> next -> next -> next = head ; if ( detectLoop ( head ) ) cout << " Loop ▁ found " ; else cout << " No ▁ Loop " ; return 0 ; }