Very nice write up about this problem that made me finally understand. The key explanation is finally the fast pointer (hare) will overlap the slower one (tortoise).
The tortoise moves one step, the hare moves two steps. When there's a loop, no matter when/where, for sure they will on the same position. Amazingly, its complexity is only O(n).
The tortoise moves one step, the hare moves two steps. When there's a loop, no matter when/where, for sure they will on the same position. Amazingly, its complexity is only O(n).
Tidak ada komentar:
Posting Komentar