Write a program to detect loop in a Linked List


Floyd’s Algorithm:

This problem can be solved by using two pointers, slow pointer and fast pointer.Both these pointers will point to head of the linked list initially. Increment slow pointer by 1 node and the fast pointer by 2 nodes. If there’s a loop, the fast pointer will meet the slow pointer somewhere.We’ll discuss in next post where they will meet.

struct node
    int data;
    struct node* next;
void detectLoop(struct node *head)
    struct node *slowPtr,*fastPtr;
    slowPtr = head;
    fastPtr = head;
    while(slowPtr!=NULL && fastPtr!=NULL && fastPtr->next!=NULL)
       slowPtr = slowPtr->next;
       fastPtr = fastPtr->next->next;
       if (slowPtr == fastPtr)
           printf("%s","Loop Detected");

Time Complexity : O(n)
Space Complexity : O(1)

One Thought on “Write a program to detect loop in a Linked List

  1. Pingback: Detect loop in linked list and remove the loop - Linked list interview programs

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation