Floyd’s tortoise and hare⌗

With two pointers:

  • tortoise move slow: move 1 step in each loop.
  • hare move fast: move 2 steps in each loop.

If there is a circle existed, tortoise and hare will meet eventually in the circle. Now both tortoise and hare are in the circle, how to figure out the beginning of the circle?

  1. We put tortoise back to the beginning they both started. Such as, the first element of the linked list.
  2. Then we move both tortoise and hare step by step, they will meet in the beginning of the circle.