Suppose you are given a linked list like this:
And you want to remove the loop in it.
A very trivial way can be storing a boolean “visited” variable which stores true or false depending on whether a node is visited or not. But we need to store this info in each and every node. This will cost us some space.
A very clever way is to use two pointer for traversing the linked list. one pointer will travel one node at a time and other node will travel two nodes at a time. we can also call the pointers as slowpointer and fastpointer. Now, if there is a loop in a linked list , these two pointers will meet at a certain node.
The above mentioned algorithm was proposed by Robert Floyd and is also called Floyd’s loop detection algorithm.
so, this is how we detect a loop in a Linked List.