I came across the algorithm question of detecting a cycle in a linked list, but the solution has to be constant space O(1).
I have looked through various proofs proving that:
- If there is a cycle, at some point the tortoise and the hare will meet. I understand that at some point, both will be within the cycle, but how do we know that they will eventually meet?
- The time complexity will equal O(N), where N = # of nodes.
I do not care about the case where we want to find the START of the cycle, only about proving that if there is a cycle, then the two pointers will meet at a point within the cycle, and that the time complexity is O(N).
None of these proofs make intuitive, logical sense to me.
Can someone PLEASE explain the two bullet points above in an intuitive manner?
If there is math in the proof, it would be great if you could explain all parts of the proof that would not make logical sense to someone without a CS degree. Thanks!