detecting the start of a loop in a singly linked link list?

Is there any way of finding out the start of a loop in a link list using not more than two pointers? I do not want to visit every node and mark it seen and reporting the first node already been seen.Is there any other way to do this?

I have heard this exact question as an interview quiz question.

The most elegant solution is:

Put both pointers at the first element (call them A and B)

Then keep looping::

• Advance A to the next element
• Advance A to the next element again
• Advance B to the next element

Every time you update a pointer, check if A and B are identical. If at some point pointers A and B are identical, then you have a loop. Problem with this approach is that you may end up moving around the loop twice, but no more than twice with pointer A

If you want to actually find the element that has two pointers pointing to it, that is more difficult. I'd go out of a limb and say its impossible to do with just two pointers unless you are willing to repeat following the linked list a large number of times.

The most efficient way of doing it with more memory, would be to put the pointers to the elements in and array, sort it, and then look for a repeat.