quick and fun visualization of cycle finding algorithms

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

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

Filters

## Recent Activity

&ldl Floyd's Algorithm has one pointer moving at 1-step per iter, and another at 2-steps per iter
This makes the initial step of "find node in loop" take 3-steps per iter
Brent's Algorithm reduces this to 1-step per iter by having one pointer at 0-steps per iter and another at 1-step per iter
By periodically updating the stationary pointer every power of 2, you'll find a node in the loop (and the loop length) faster
Now that you have the loop length, you can use the same method as before to find the start of the cycle

View original message on Discord

&ldl Added sliders, hit testing, and lots of polish

View original message on Discord

&ldl added some sliders, hit testing, and lots of polish

&ldl demonstrating a simple cycle detection algorithm

• Find node in loop (one moves at 2x speed)
• Compute length of loop
• Compute start of loop
2 ways to get to the start of the loop:
• Take s steps
• Take s + l steps -> equivalent to taking l + s steps
View original message on Discord

just some loop-de-loops &ldl for now

View original message on Discord