Back to course home
0% completed
Vote For New Content
If you didn't understand why this works (because explanation is very poor)
Aydar Nabiev
Dec 15, 2025
A linked list with a cycle looks like this:
μ(mu) = number of nodes before the cycle starts (distance from head to cycle entry)λ(lambda) = cycle length
Example shape:
head → ... (μ nodes) ... → [CYCLE ENTRY] → ... → (λ nodes loop back)
- Compute cycle length
λ. - Put two pointers at
head:
p1 = headp2 = head
- Move
p2ahead byλsteps. - Move both
p1andp2one step at a time. They will meet at the cycle entry.
Why moving ahead by λ makes them meet at cycle start
Key invariant
At all times during step 4:
p2is exactlyλnodes ahead ofp1along the list.
Because you advanced p2 by λ at the start, and then you move both pointers equally (1 step per iteration), the gap stays constant.
I suggest if you still didn't understand, draw this part
head → ... (μ nodes) ... → [CYCLE ENTRY] → ... → (λ nodes loop back)
This part is constant for no matter how many nodes are in μ and λ, that's why this works. Why authors couldn't clarify this though - this is the key to understanding this algorithm, right? They were pretty good at explaining previous tasks, but this one imo needs more thought put into it.
0
0
Comments
Comments