4 ms·
The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If
by mankyd 12y ago
The "tortoise" pointer does a standard traversal - one at a time. The "hare" pointer goes from one node to the next _and then the next_ - i.e. two at a time. If the hare hits a null node, there's no loop. If the hare hits a cycle, it will eventually run back into the tortoise and there's a loop.
- pessimizer 12y agoI must have learned this algorithm in school, but completely forgot it. My naive implementation was 2), but this is the first explanation on this page that made Floyd’s cycle-finding algorithm click for me:) Now I can't unknow it - thanks for the clarity and concision!