Write an algorithm to find loop in a linked list?

Start with two pointers (ptr1 and ptr2), both pointing to the first node of the given list. Now traverse the linked list with ptr1 two nodes forward and ptr2 one node forward. Stop when ptr1 reaches to end of linked list or both the pointers pointing to same node i.e. ptr1 = ptr2.
1. Ptr1 = ptr2 then linked list contain loop.
2. If ptr1 reached end of the list that means list doesn’t contains loop.

There can be other solution for this problem if we are allowed to change structure of list node. We can add marker field to each node and start traversing the list from beginning and as soon as we visit a node, we’ll mark the field as ‘visited’. If we find any node with marker field as ‘visited’ that means list contains loop.

March 7, 2008 | Filed Under Algorithm