The interviewer is looking to see if you know a trick that is known officially as Floyd's cycle-finding algorithm
, or Tortoise and hare
unofficially.
The idea is to advance two pointers in a loop, one moving twice per iteration, and the other only once. If the fast-moving pointer catches up to the slow-moving one from behind, the list has a cycle.
This algorithm detects a cycle in O(n)
time and O(1)
storage. The "slow" pointer goes through the list no more than once, so it is fair to say that the algorithm finds an answer in a single traversal.
In my opinion this algorithm makes a poor interview question, because it is somewhat hard to come up with it on the spot, unless you know it ahead of time. At the same time, this is not a an algorithm that is used so widely that everyone must know it, making me wonder why anyone would ask about it in an interview.