Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Just in case performance matters, there is a more efficient way: have the tortoise stay in place and advance the hare only one node at a time, and assign the hare to the tortoise every time a power of 2 number of steps have been made. This is known as Brent's algorithm, and it requires fewer advancements than the original tortoise and hare algorithm by Floyd.

Another notable advantage of Brent's algorithm is that it automatically finds the cycle length, rather than (in Floyd's case) any multiple of the cycle length.

https://en.wikipedia.org/wiki/Cycle_detection#Brent's_algori...



https://rosettacode.org/wiki/Cycle_detection

Cycle detection in (currently) 44 languages. Most (all?) use Brent's algorithm. They're operating on an iterated function but converting most of these to detect cycles in a linked list would be straightforward.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: