Linked List Cycle II: Understanding the math behind finding the start of a linked list loop
The discussion and video solutions I found for Leetcode Linked List Cycle II either glossed over the math that explained why the solution worked, or had a bunch of equations that didn’t make intuitive sense to me.
So I asked my friend Carles, an AI scientist who enjoys working on math problems, for help. This article is a synthesis of our one-hour virtual white-boarding session.
Floyd’s Tortoise and Hare Algorithm
We know that in order to tell whether a linked list has a cycle in it, we use Floyd’s tortoise and hare algorithm: past the first node, if the “hare” pointer moving 2 nodes forward at a time eventually reconvenes with the “tortoise” pointer moving one node at a time, we have irreconcilable proof that our hare has lapped up to our tortoise (usually a few times by then to be honest), where the only way for that to happen past the starting point is in a loop.
[ insert image of a regular linked list, and one with a loop ]
As a result, if the hare ever lands on the same node as the tortoise, then it proves that our linked list has a loop.
Otherwise, if there wasn’t a loop, then the hare would hit the end of the list and run out of nodes to step through, making it impossible for the tortoise to ever catch up to the same node.
Now, this information is important. For the rest of this article, assume that we’re always working with a linked list with a loop in it, because now we want to prove how to calculate where the start of the loop is.
Part 1: How Far Ahead The Hare Is From the Tortoise
let i = number of steps the tortoise has stepped through after any number of iterations. i represents the index of a node.
In comparison to the the tortoise, the hare steps through nodes at a 2*i rate.
What this means is that at any given point, the hare is always i steps ahead of the tortoise, where i is the number of steps the tortoise has taken and 2*i is the number of steps the hare has taken. (2*i - i = i)
At any given point also includes the point when the hare overlaps the tortoise: when they are at the same node even though the rabbit is always i steps ahead of the turtle.
[ insert video of tortoise and hare node in linked list ]
Part 2: Older Brother And Younger Brother: Loopity Loops
Now let’s think about the the length of the loop.
let o = length of the loop, or how many steps it takes to start at the beginning of the loop and end at the same point, the beginning of the loop.
We have an older brother and a younger brother. They both go through life at the same rate; they each step through one node, one step at a time, but older brother has a head start because he was born however many years earlier (including 0, in the case of twins).
We can think of the loop as adulthood because adult responsibilities never end.
For now, let’s ignore the straight part of the list and focus on just the loop. Say that we’re at the start of our loop, and we mark it as such. Younger brother hasn’t been born yet. Older brother takes a few steps from the beginning of the loop. Then, little brother enters the start of the loop.
Since they’re both walking at a rate of one step per iteration, the ONLY way they’d be able to ever meet, ever, is inside the loop. Choose any point inside the loop for them to meet, and in order for that to happen, that must mean that older brother and younger brother must have matched nodes for the first time at the start of the loop. Maybe they have a child in the same year, but it’s older brother’s third child and younger brother’s firstborn.
[ insert video of iterating thru just loop, or gif with START and END placards ]
That means maybe the older brother has done 1 complete lap of the loop (o) by the time younger brother starts in the loop. Or 2 complete laps of the loop (2*o) by the time younger brother starts in the loop. Or 3 complete laps of the loop (3*o), etc. by the time younger brother starts in the loop.
And… this also works when we reintroduce the straight part of the list back into the picture.
[ insert video of iterating thru loop incl straight part ]
If we start younger brother on any part of the straight part of the list, and start older brother o or any multiple of o ahead of him, they meet…at the entrance of the loop!
[ insert video of iterating thru loop anywhere ]
No matter how many factors of o the older brother’s head start is, the two brothers always meet anytime they’re both inside the loop: the loop is limitless and enduring, and as the limit of the number of iterations approaches infinity, the brothers convene so long as the older brother had a head start that was some multiple of o.
Part 3: Putting it All Together
Always true:
At any given iteration, the tortoise is i steps in, the hare is always 2*i steps in, and consequently the hare is always i steps ahead of the tortoise.
Now, let 2*I be the specific number of steps the hare has made by the time it meets the tortoise on the same node in the loop, and I the specific number of steps the tortoise has made by the time they convene.
Instead of thinking of the hare as moving twice as fast as the tortoise to reach the convening node, we can also think of the hare as getting a ‘head start’ of I steps relative to the start of the list, and thenceforth moving at an amortized rate of one node at a time. You can also think of it as taking the integral of its speed advantage.
For it to be possible for them to meet within the loop, this must mean that the head start of I is some multiple of o.
Well, I steps in is also where the tortoise ends up when the hare catches up to it.
The result?
So, we take the node location where the hare and tortoise convene. The tortoise’s location at the node I steps in now becomes big brother’s location.
And then… little brother starts from the beginning of the list, older brother starts from where the hare met the tortoise… and THEY MEET AT THE BEGINNING OF THE LOOP!!!!!
[ insert video of example ]
