But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.
You're in!
You 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 method ContainsCycle 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 method work for both?
We can do this in time and space!
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
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 fastRunner had 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:
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 fastRunner didn't skip over slowRunner! (This is a proof by contradiction.)
Since fastRunner can't skip over slowRunner, at most slowRunner 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 .
Log in or sign up with one click to get immediate access to free mock interview questions
We'll never post on your wall or message your friends.
Reset editor
Powered by qualified.io