I saw this question on the Related section and after going through some of the discussions, i see that the most common solution is the hare and tortoise algorithm. but another suggested solution that i saw (which is what i would have done) is to include the a third instance variable of a Node class that would keep track of nodes it has visited, like a boolean variable. so is this considered a valid solution?
Add a comment
|
1 Answer
Your solution is definitely a valid one, in the sense that it will get the job done.
However, the problem of detecting a loop is usually formulated with the additional constraint of using O(1) additional memory. The hare and tortoise algorithm satisfies this constraint, while your algorithm does not: it requires O(N) additional memory to store the per-node booleans.
answered Sep 10, 2012 at 19:54
Sergey Kalinichenko
729k85 gold badges1.2k silver badges1.6k bronze badges
1 Comment
false
@ueg1990: Brent's algorithm is clearly better than both. See this answer