News for hackers. Stuff that matters.
Re:The Worst Programming Interview Question by mankyd on Friday June 27, 2014 @10:25AM (#7954029)
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.
Re:The Worst Programming Interview Question by pessimizer on Friday June 27, 2014 @11:40AM (#7954460)
I 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!