In the given linked list, find whether there is loop or not
If there is a loop in the linked list then some node in the linked list will be pointing to one of the previous nodes in the same linked list.
Example
Time complexity : O(n)
Algorithm
We use Floyd`s Cycle Finding method,
a. Traverse linked list with two pointers.
b. Move slow pointer by 1 step and fast by 2 steps.
c. If slow and fast meets then that means there is a loop, and if they doesn’t there is no loop.
C++ Program
#include <bits/stdc++.h> using namespace std; struct LLNode { int data; struct LLNode* next; }; /* Function to insertAtBeginning a node */ void insertAtBeginning(struct LLNode** head, int dataToBeInserted) { struct LLNode* curr = new LLNode; curr->data = dataToBeInserted; curr->next = NULL; if(*head == NULL) *head=curr; //If this is first node make this as head of list else { curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head *head=curr; } //O(1) constant time } //display linked list void display(struct LLNode**node) { struct LLNode *temp= *node; while(temp!=NULL) { if(temp->next!=NULL) cout<data<<"->"; else cout<data; temp=temp->next; //move to next node } //O(number of nodes) cout<<endl; } int DetectLoop(struct LLNode *list) { struct LLNode *slow = list, *fast = list; while(slow && fast && fast->next ) { slow = slow->next; fast = fast->next->next; if (slow == fast) { cout<<"This list contains loop"<<endl; return 1; } } return 0; } //Main function int main() { struct LLNode* head = NULL;//Initial list has no elements insertAtBeginning(&head, 6); insertAtBeginning(&head, 5); insertAtBeginning(&head, 4); insertAtBeginning(&head, 3); insertAtBeginning(&head, 2); insertAtBeginning(&head, 1); //create a loop for testing head->next->next->next->next = head; DetectLoop(head); return 0; }