2.4 findBeginning

Given a circular linked list, implement an algorithm which returns node at the begin-
ning of the loop.

I'm still wrapping my head around this algorithm. Definitely not something I would've thought of on the spot, especially the second part.

Here's the algorithm steps.

1. Find out if it actually does have a loop by sending two runners through, one at normal pace, one at double the pace. If they hit, there is a loop.

2. Realize that the place it meets in is significant. Let's say it the list is this: 1->2->3->4->5->6->7->8->9->3. If we send "A" through the loop twice as fast as "B", they will actually always meet two after the "3", the beginning of the circle. Why is that?

Well. If there is an x amount of space to the first circular node, then by the time "B" the circular node actually enters the cycle, A will be x amount ahead of B. (If B goes 3, A will go 6. Therefore A is 3 ahead.)

Now, when will they meet? Well, if two runners at the track start at the same position, "A" runner going twice as fast as "B", "A" runner would lap "B" runner after two laps. However, what if "A" started with a "x" distance headstart? They would actually meet at 2 laps - x distance.

So here's what we do for the algorithm. We send A and B until they meet, A going twice as fast. We leave A at the meeting position, send B to the beginning. They are now both x distance away from the beginning of the cycle. So,now we move them forward at the same pace, until they meet. That is where the beginning is.