|
|
|
|
|
by function_seven
2969 days ago
|
|
If no cycle is longer than 50 boxes (~30% chance of that being true), then by starting with the box that matches your number, you have a 100% chance of navigating to the box containing your number before your 50-box limit is reached. It’s impossible to start in the wrong cycle, because that cycle contains neither the pointer or the value. You have to find your pointer in a circular linked list. But it’s only singly-linked, so you start just in front of it and work around the links the long way. 30% of the time, all the lists are 50 elements or shorter, meaning everyone is guaranteed to succeed. |
|