Hacker News Reader

Comment by sherincall | Hacker News Reader

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.

View on HN

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