Date: 04/20/05 (Algorithms)    Keywords: no keywords

My boss and I were discussing a tricky one (tricky for us atleast):
You are given a simple one-way linked-list. You are assured that at most one loop exists. You have to identify the node at which the loop begins in the most efficient manner.

Example:
Node 1 --> Node 2--> Node 3 --> Node 4 --> Node 5

If node 5 points back to node 3, node 3 should be the answer.

But the problem is that you cannot add fields to the linked list (e.g., a 'visited' mark). You can't build a duplicate linked list to clone the original linked list as you traverse it, since you will double the memory requirement. And ofcourse, O(n^2) time solutions are absolutely unwelcome.

Solutions anyone? I'm still working on it. Will self-reply if a Eureka moment hits me. I have a feeling I am missing the solution by a whisker.

Source: http://www.livejournal.com/community/algorithms/52678.html