### 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