Finding or detecting a loop/cycle in Link List.
One of famous questions asked in programming technical interviews is “Finding a loop in a linear linked list”. Apparently this problem is easy, but if one has interest in Algorithms and Complexity Theory this is a very interesting problem also related to number theory.
The most famous method to solve this problem is to use Floyd’s algorithm to find cycle in lists also known as “The Hare and the Tortoise Algorithm”, intersting :). If a list has a cycle in it, it can be detected using this algorithm. This algorithm can also be used to find cycles in “PseudoRandom Sequences”. The algorithm to find the cycle in linked list is as follows.
Take two pointers pointing to head. Now advance one pointer to one node and other pointer to two nodes each time while iterating. This is the simple algorithm, and that’s it. If the first pointer enters the loop (cycle part of algorithm) it is guaranteed that the second pointer will be at some node in the loop at the same time when other pointer is pointing to same node. The result may come out by some iteration, but it’s assured. That’s because one pointer is iterating each node in loop and other is iterating alternating nodes, so at first or second iteration while in the loop it will catch the first pointer at same node. This is indeed a very good find. I tried this with moving the second pointer to three nodes at one time and it worked also though I had to iterate many times. By using this approach we can also find the number of nodes in the loop which is an interesting thing to try.

January 19, 2007 at 3:51 pmgeometry and triangle