linked list loop - cycle start element and list length

Question

I read about loop in linked list detection algorithm and I doubt

1) How to detect the "meeting element". For example, in the follow case - how to detect that the meeting is at the 3nd element?

2) How to detect the list's length (in case above - 6)

Both questions in running time O(n) , memory O(1).

Answer 1

Using tortoise-hare algorithm(floyd's cycle detection), we can find the loop in a given a list.

i.e If we move two pointers, one with speed 1 and another with speed 2, they will end up meeting if the linked list has a loop. Why? Think about two cars driving on a track—the faster car will always pass the slower one!

The tricky part here is finding the start of the loop. Imagine, as an analogy, two people racing around a track, one running twice as fast as the other. If they start off at the same place, when will they next meet? They will next meet at the start of the next lap.

Thus, after identifying the loop, if we move n1 back to Head and keep n2 at MeetingPoint, and move them both at the same pace, they will meet at LoopStart(Meeting Element).

Then, to find the length, when moving n1 back to head define a length variable. Now increment length variable on each move. After idetifying LoopStart, keep n1 ptr as such and move the n2 ptr and inc length for each move. When n2->next == n1, return the length.

This would have running time O(N), Space complexity O(1)