Associated list loop - loop trigger and list length

Question

I read about the loop in a linked list detection algorithm and I doubt that

1) How to define a “meeting item”. For example, in the following case - how to determine that the meeting is on the 3rd element?

2) How to determine the length of the list (in the case above - 6)

Both issues at run time are O (n), memory is O (1) .

Answer 1

Using the tortoise-hare algorithm (detecting the cycle of floyds), ​​we can find the cycle in this list.

ie If we move two pointers, one at speed 1 and the other at speed 2, they will occur if the linked list has a loop. What for? Think of two cars moving along a track - the faster the car will always go slower!

The hard part here is finding the beginning of the cycle. Imagine how an analogue, two people rush along a track, one running twice as fast as the other. If they start in the same place, when will they follow next time? They will follow at the beginning of the next lap.

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

Then, to find the length, move n1 back to the head and set the length variable. Now change the length of the variable at each step. After idetifying LoopStart, save n1 ptr as such and move n2 ptr and inc length for each move. When n2-> next == n1, return the length .

This will be O (N) runtime, O (1) space complexity

Answer 2

When using the Floyd loop search algorithm, fast and slow links will not appear in the third element, but instead in the fourth. Their positions begin with (1,2) and move as follows: (1,2) → (2,4) → (3,6) → (4,4).

I would think that to find out exactly where the loop is, you need O (n) space, as well as O (n) time.

Answer 3

I do not think that you can do this in O (n) time using only O (1) working memory.

There are n different candidates for the “assembly element” (beginning of the loop), and in O (1) memory you can only record a fixed number of them. This should not be a problem if you can go around the structure many times, but if you can only check a fixed number of nodes in each walk, you will need to cross the structure n times, taking O (n²) total time.

A simple solution is to abandon the O (1) memory requirement. Go around the loop once and save the pointers to the nodes in the hash table until you click on the duplicate entry. Expected time O (n), memory usage O (n).