Home » Interview Questions » LinkedList Interview Questions » Detect a loop in the Linked List

Detect a loop in the Linked List


()

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

READ  Merge K Sorted Linked Lists

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions