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.


Time complexity : O(n)


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
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
        //O(1) constant time
//display linked list
void display(struct LLNode**node)
    struct LLNode *temp= *node;
            temp=temp->next; //move to next node
        //O(number of nodes)
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;
    return 0;

Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions