Answer Posted / sujith
Simultaneously go through the list by ones (slow iterator)
and by twos (fast iterator). If there is a loop the fast
iterator will go around that loop twice as fast as the slow
iterator. The fast iterator will lap the slow iterator
within a single pass through the cycle. Detecting a loop is
then just detecting that the slow iterator has been lapped
by the fast iterator.
This solution is "Floyd's Cycle-Finding Algorithm" as
published in "Non-deterministic Algorithms" by Robert W.
Floyd in 1967. It is also called "The Tortoise and the Hare
Algorithm"
| Is This Answer Correct ? | 11 Yes | 2 No |
Post New Answer View All Answers
What is a program?
What is wrong in this statement?
What is the package for freshers(Non IIT) in amazon(hyderabad). And what is the same for those who are a contract employee.
Explain a pre-processor and its advantages.
How can you restore a redirected standard stream?
What is a far pointer in c?
What is double pointer in c?
How can you draw circles in C?
There seem to be a few missing operators ..
explain what are actual arguments?
Differentiate between null and void pointers.
When c language was developed?
What is the right type to use for boolean values in c?
please send me the code for multiplying sparse matrix using c
Is c++ based on c?
