Test if single linked list is circular by traversing it only once
I am a fresher and I was asked this question in a recent interview I gave.
The question was --- By traversing each element of linked list just once find if the single linked list is circular at any point.
To this I answered that we will store reference of each node while traversing the list in another linked list and for every node in the list being tested we will find if the reference exists in the list I am storing the references.
The interviewer said that he needs a more optimized way to solve this problem.
Can anyone please tell me what would be a more optimized method to solve this problem.
PS: By circular at any point I mean this. http://s22.postimg.org/g0iwevfnl/2013_06_30_15_56_34_362.jpg
Answer
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.