Given a linked list, can you find:
- Whether it has a cycle?
- How long the cycle is?
- Where the cycle starts?
Can you do it in O(n) time?
Can you do it in O(1) memory?
How about both?
The 2 algorithms I show here which accomplish this are Floyd's and Brent's Algorithm
They're what shows up on Wikipedia's page for Cycle Detection
Technically, the first snippet I showed isn't Floyd's algorithm, but a pedagogical hybrid
This uses the same method to find s as Brent's algorithm for simplicity
but it takes l more steps than if you're a bit more careful
First, consider where the tortoise and the hare end up after s steps
The hare is s % l steps ahead of the tortoise and s' steps from lapping it
Note, this is true even when l < s, and that 0 <= s' < l
Now, look what happens after s' steps
The hare has caught up to the tortoise and is s steps away from the loop start
So, reset 1 node and walk them at the same pace, counting each step
We find s exactly when they collide with one another
This does so in 2s steps, the recordings do l steps followed by 2s steps