CareerCup

Note what the Floyd algorithm says a fast runner (hare) and a slow runner (tortoise), it doesn't say how fast they should be. For any step size >1 the algorithm will work to find the cycle/loop. It may take more or less steps to finish, depending on the loop size, the collision point, and the step size.

Firstly, step size of 2 is practical when iterating the linked list. Secondly and more importantly, step size of 2 is needed to calculate the collision point and/or the length of the loop.

Here is the explanation from Wikipedia:
The key insight in the algorithm is that, for any integers i ≥ μ and k ≥ 0, xi = xi + kλ, where λ is the length of the loop to be found. In particular, whenever i = kλ ≥ μ, it follows that xi = x2i. Thus, the algorithm only needs to check for repeated values of this special form, one twice as far from the start of the sequence than the other, to find a period ν of a repetition that is a multiple of λ. Once ν is found, the algorithm retraces the sequence from its start to find the first repeated value xμ in the sequence, using the fact that λ divides ν and therefore that xμ = xν + μ. Finally, once the value of μ is known it is trivial to find the length λ of the shortest repeating cycle, by searching for the first position μ + λ for which xμ + λ = xμ.

The algorithm thus maintains two pointers into the given sequence, one (the tortoise) at xi, and the other (the hare) at x2i. At each step of the algorithm, it increases i by one, moving the tortoise one step forward and the hare two steps forward in the sequence, and then compares the sequence values at these two pointers. The smallest value of i > 0 for which the tortoise and hare point to equal values is the desired value ν.

Three times or more might not always work. For instance, in the three case

consider the scenario where you end up in a situation like this;

A  ---->  B

^            |
 |             |
 |            V
  
 D <----- C

You have the slow pointer pointing at C and the fast one at B.

Basically, the distance between the slow and the fast will always change by a multiple of T-1, where T is the speed of the fast pointer.

In case of T=3, this means the distance between the two will always be either even or odd. If you start with odd, they will never meet.

Consider this scenario.

1->2->1

Moving the 2nd pointer by 3 might not work in this case.

It seems to work in a list larger than 3, like the ones below.

1->3->5->2->4->2....

1->3->5->2->4->5...

Please let me know if I missed something.

The fast pointer could be 2x , 3x or in general any times faster and still we would be able to detect the loop in the linked list . It is only for easier calculation of the meeting point (starting point of loop) and which helps in calculating length we chose fast pointer as 2x

class Node
{
public:
	int data;
	Node *next;
};
Node* findCyclic(Node* root)
{
	Node* t1=root;
	Node* t2=root;
	while(t1!=NULL&&t2!=NULL)
	{
		t1=t1->next;
		t2=t2->next;
		if(t2)
			t2=t2->next;
		if(t1==t2)
			return t1;
	}
	return NULL;
}
Node* findCollison(Node* root)
{
	Node* loop=findCyclic(root);
	if(!loop)
		return NULL;
	Node* t1=root;
	while(loop!=t1)
	{
		loop = loop->next;
		t1=t1->next;
	}
	return loop;
}

A snippet from stackoverflow(by Anurag):
Here's an attempt at an informal proof.

The shape of the cycle doesn't matter. It can have a long tail, and a loop towards the end, or just a loop from the beginning to the end without a tail. Irrespective of the shape of the cycle, one thing is clear - that the tortoise pointer can not catch up to the hare pointer. If the two were ever to meet, the hare pointer has to catch up the to tortoise pointer from behind.

With that established, consider the two possibilites:

hare pointer is one step behind the tortoise pointer.
hare pointer is two steps behind the tortoise pointer.
All greater distances will reduce to one or two eventually.

Assuming the tortoise pointer always moves first (can be the other way around too), then in the first case, the tortoise pointer takes one step forward. Now the distance between them is 2. When the hare pointer takes 2 steps now, they will land on the same node. Here's the same thing illustrated for easier understanding. Too much text can get in the way.

♛ = hare
♙ = tortoise
X = both meet

..♛♙... #1 - Initially, the hare is one step behind the tortoise.
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind.
....X.. #3 - Next, the hare takes two steps and they meet!
Now let's consider the second case where the distance between them is 2. The slow pointer moves one step forward and the distance between them becomes 3. Next, the fast pointer moves forward two steps and the distance between them reduces to 1 which is identical to the first case in which we have already proved that they will meet in one more step. Again, illustrated for easier understanding.

.♛.♙... #1 - Initially, the hare is two steps behind the tortoise.
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart.
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case.
Now, as to why this algorithm is guaranteed to be in O(n), use what we've already established that the hare will meet the tortoise before it moves ahead. Which means that once both are inside the loop, before the tortoise completes another round, it will meet the hare since the hare moves twice as fast. In the worst case, the loop will be a circle with n nodes. While the tortoise can only complete one round in n steps, the hare can complete two rounds in that time. Even if the hare missed the tortoise in its first round (which it will), it's definitely going to catch up to the tortoise in its second round.

Well i don't think there should some difference in the speeds of the two pointers. Logically, in a circular loop if two persons are moving at the same speed, they will never meet.

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.
Now, let’s suppose Fast Runner had a head start of k meters on an n step lap. When will they next meet? They will meet k meters before the start of the next lap. (Why? Fast Runner would have made k + 2(n - k) steps, including its head start, and Slow Runner would have made n - k steps. Both will be k steps before the start of the loop.)
Now, going back to the problem, when Fast Runner (n2) and Slow Runner (n1) are moving around our circular linked list, n2 will have a head start on the loop when n1 enters. Specifically, it will have a head start of k, where k is the number of nodes before the loop. Since n2 has a head start of k nodes, n1 and n2 will meet k nodes before the start of the loop.
So, we now know the following:
1. Head is k nodes from LoopStart (by definition).
2. MeetingPoint for n1 and n2 is k nodes from LoopStart (as shown above).
Thus, 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.