Hacker News Reader

Comment by huhtenberg | Hacker News Reader

Hacky, trashes CPU cache, the code itself is on a sloppy side and, most importantly, it lacks the elegance of the original solution.

So I beg to differ, it's not really "better" by any metric.

View on HN

It was tongue-in-cheek (see the smiley face), your critiques are all spot on, but there is one thing where it is objectively better:

Tortoise and hare can only detect that a cycle exists. This hack will tell you exactly which node the cycle starts on. That means that if you want to e.g. repair a list, you can just cut that last link and set it to either null or root. Granted, this wasn't the original problem.

Tortoise and hare can actually tell you which node the cycle starts on.

  1 -> 2 -> 3 -> 4 -> 5 -> 6
            ^              |
            |______________|

  Step:       0 1 2 3 4
  Tortoise:   1 2 3 4 5 
  Hare:       1 3 5 3 5 <- pointers reference same node, cycle exists

Then create another tortoise pointer at the head, iterate until both tortoises point to the same node.

  Step:       0 1 2
  Tortoise:   5 6 3
  Tortoise2:  1 2 3 <-cycle starts at 3

Reply on news.ycombinator.com