Just No more free questions left!
Upgrade NowYou have a singly-linked list and want to check if it contains a cycle.
A singly-linked list is built with nodes, where each node has:
For example:
A cycle occurs when a node’s next points back to a previous node in the list. The linked list is no longer linear with a beginning and end—instead, it cycles through a loop of nodes.
Write a function contains_cycle that takes the first node in a singly-linked list and returns a boolean indicating whether the list contains a cycle.
Careful—a cycle can occur in the middle of a list, or it can simply mean the last node links back to the first node. Does your function work for both?
We can do this in time and space!
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.
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 fast_runner equals slow_runner. But how long will that take?
First, we notice that when both runners are circling around the cycle fast_runner can never skip over slow_runner. Why is this true?
Suppose fast_runner had just skipped over slow_runner. fast_runner would only be 1 node ahead of slow_runner, since their speeds differ by only 1. So we would have something like this:
What would the step right before this "skipping step" look like? fast_runner would be 2 nodes back, and slow_runner would be 1 node back. But wait, that means they would be at the same node! So fast_runner didn't skip over slow_runner! (This is a proof by contradiction.)
Since fast_runner can't skip over slow_runner, at most slow_runner will run around the cycle once and fast_runner 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 .
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.
Powered by qualified.io