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"); exit(0); } } }
Time Complexity : O(n)
Space Complexity : O(1)
Pingback: Detect loop in linked list and remove the loop - Linked list interview programs