We'll never post on your wall or message your friends.
Once you're logged in, you'll get free full access to this and 4 other questions.
time and space.
The runtime analysis is a little tricky. The worst case is when we do have a cycle, so we don't return until fastRunner equals slowRunner. But how long will that take?
First, we notice that when both runners are circling around the cycle fastRunner can never skip over slowRunner. Why is this true?
Suppose fastRunnerhad just skipped over slowRunner. fastRunner would only be 1 node ahead of slowRunner, since their speeds differ by only 1. So we would have something like this:
[ ] -> [s] -> [f]
What would the step right before this "skipping step" look like? fastRunner would be 2 nodes back, and slowRunner would be 1 node back. But wait, that means they would be at the same node! So fastRunnerdidn't skip over slowRunner! (This is a proof by contradiction.)
Since fastRunner can't skip over slowRunner, at mostslowRunner will run around the cycle once and fastRunner will run around twice. This gives us a runtime of .
For space, we store two variables no matter how long the linked list is, which gives us a space cost of .
How would you detect the first node in the cycle? Define the first node of the cycle as the one closest to the head of the list.
Would the program always work if the fast runner moves three steps every time the slow runner moves one step?
What if instead of a simple linked list, you had a structure where each node could have several "next" nodes? This data structure is called a "directed graph." How would you test if your directed graph had a cycle?