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;
}