detecting loops in linked lists

[zameericle]

hello,

curious on the different algorithms available to detect loops in linked lists.

One algorithm I heard off was the "Tortouise & Hare" (sp??) where you have two pointers on the list, on of which moves twice as fast. Eventually the two pointers will meet up..

Are there any other algorithms?

thanks

Zameer

[Manish Malik]

Using 2 iterators, one moving twice as fast as the other, is te most popular technique to do it.

Another approach can be: If the linked list consists of objects of a class, include a flag bit in the class definition. While traversing, check if the flag bt is already turned on. If it is on, there's a loop. Otherwise, turn it on and continue traversal.