Test if single linked list is circular by traversing it only once

Question

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 1

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.

Answer 2

I doubt that the interviewer goal was to see if you know the Floyd's cycle-finding algorithm. The goal of such a question would be to see if you understand data-structures concepts such as lists, binary trees and hashes.

The main problem with your answer is that the algorithm you gave have a complexity of O(n^2), i.e. O(n) for traversing the original list * O(n) for checking if each node exists in the second list, in each iteration.

When the interviewer asked you to optimize your answer, you could have suggested replacing the second linked list with another data-structure that provide faster lookup than O(n). For instance a binary tree has an O(logn) lookup complexity and a hash has an O(1) lookup complexity (not always but this is a common assumption), which is significantly faster than using a second linked list that have a lookup complexity of O(n).

So an O(n) solution would be to replace your second linked list with a hash (i.e. HashMap, HashSet, etc).

Of course the Floyd's cycle-finding algorithm is a more elegant solution to this problem because it has a better memory complexity (i.e. no need to store the visited nodes in memory).