how to find that is there any loop exist in the link list using two pointers?

Question

Possible Duplicate:
How to determine if a linked list has a cycle using only two memory locations.

hello i have been asked in an interview that how can i find a loop exists in a link list using only two pointers.

i have done the following:

1) find the center of the link list each time

2) by iterating this at the end both the pointers will be pointing the same node if not pointing the same node and finds a null then there is no loop in link list.

is there any efficient method to do this...?

thanx in advance.

Answer 1

I think you're looking for Floyd's cycle detection algorithm, also known as the "Tortoise and Hare algorithm". The idea is to set one pointer (the "tortoise") to the first node in the list, and another pointer (the "hare") to the next item. Then in each step, the "tortoise" pointer is advanced one position, and the "hare" is advanced two steps. After each iteration, the pointers are checked to see whether they point to the same node. If this ever occurs, that node must be part of a cycle.

To find the start of the cycle, one of the two pointers is repositioned to the start of the list, while the other is left at its current position. Then both pointers are advanced, this time by a single step per iteration for both pointers, until they meet again. This (second) meeting point is the first node in the cycle.

Answer 2

Move one pointer 1 node per iteration, move the other pointer 2 nodes per iteration. If the fast node sees null, there is no loop, if the fast pointer sees the slow pointer, there is a loop. Solved.

The solution is a famous one modeled after the turtle and the hare.

Answer 3

The generic solution to this is to use two pointers and a loop. One pointer moves to next node on each loop iteration. The other pointer moves only every second iteration. If you reach NULL before your reach first == second your list does not have a loop.