Cycle/Loop Detection in Linked List
A cycle/loop in a single linked list can be detected easily if there's a node which points to some other previous node in the list or to itself. The program below detects the cycle in the single linked list with 'head' as root node pointer passed to the function cycledetection(), and will return the Boolean true if a cycle is detected or else false.
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | bool cycledetection(Node* head) { Node *temp,*p; //pointer variables int f,i; p=head; f=0; while(p!=NULL) //Traverse the List { temp=head; while(temp!=p) //Traverse upto p { if(p->next==temp) //Check for cycle { f=1; break; } temp=temp->next; //Point to next node } if(f==1) //Check for flag break; else p=p->next; } if(f==1) //If there's a cycle then return true else false return true; else return false; } |
0 comments:
Post a Comment