Re:My Google Interview
by brown9-2 on Friday July 16, 2010 @09:33AM
(#1521067)
What do you mean by "accounting" information?
In the real-world I'd probably just brute-force it and keep around a set of elements already gone over.
That is what is meant by accounting information - keeping track of the elements in the list you've visited.
I believe the generally accepted answer for this question is to use two iterators, one moving faster (two elements at a time) than the other (one element at a time). If there is a cycle in the list, at some point the two iterators will be pointing at the same node. Otherwise, the iterators will reach the end of the list, meaning no cycle exists.
In the real-world I'd probably just brute-force it and keep around a set of elements already gone over.
That is what is meant by accounting information - keeping track of the elements in the list you've visited.
I believe the generally accepted answer for this question is to use two iterators, one moving faster (two elements at a time) than the other (one element at a time). If there is a cycle in the list, at some point the two iterators will be pointing at the same node. Otherwise, the iterators will reach the end of the list, meaning no cycle exists.