Welcome back.
In this video, let's try to understand why this distance over here is going to be equal to the distance
over here.
Right.
So we have to move one two nodes from the head to reach this node.
And then from here also if we move one and then the second node we are again going to reach over here.
So we are going to try to understand why these two distances are the same.
So that's this proof over here.
Now I've just set it up over here.
Let's say the nodes which are not part of the cycle is equal to x.
And then let's say this is the meeting point.
So the distance from the first node of the cycle to the meeting point is equal to m.
And then let's say the length of the cycle is equal to c.
For example in this case that's 3456 and seven.
So the cycle length is seven.
And over here this is 3456.
So m is equal to six and x is equal to two.
For example.
Now if the meeting is going to happen over here then the hare and the tortoise have to reach over here.
Now when the hare reaches over here let's say it has done n cycles over here and then finally reached
back over here.
So we can say the hare has moved x plus n into C, which is n cycles plus m, right.
And in the same time we can say that the tortoise has done x plus m nodes.
It has travelled x plus m nodes.
All right.
So this is the distance or the number of nodes that the hare and the tortoise has travelled.
Now we know that the hare is traveling at twice the speed of the tortoise.
So we can see that n h will be equal to two times n into t.
That is, the number of nodes that the hare travels is going to be twice the number of nodes that the
tortoise is going to travel.
So let's substitute these two into this equation over here.
So we get x plus NC plus m is equal to two times x plus m.
And that's equal to two x plus two m.
So let's try to simplify this.
Now this simplifies to NC is equal to x plus m right.
So NC is equal to x plus m.
Now if NC is equal to x plus m then we can say that x is equal to NC minus m.
So I've just taken m to the left hand side.
So x is equal to NC minus m.
Now over here we have x nodes.
So to reach over here the pointer which is over here has to do one two.
It has to do two two moves right.
It has to move two times.
So if this pointer is traveling x nodes.
Then we can see that if the pointer p two moves NC minus m nodes, right?
So I know that the number of times they are moving is the same.
Right?
So when P is moving over here, this node also is moving the same number of times because we are moving
them simultaneously.
The only thing that we are trying to prove is that when p is moving x no x times it's going to reach
over here.
And this one also is going to reach over here.
So when p is traveling x nodes because x is equal to NC minus m, we can say that p two which is this
pointer over here travels NC minus m nodes.
That is true that we know because they are traveling together now NC minus m, I can rewrite it as n
minus one c plus c minus m.
So I'm just taking one c out of NC.
So this is n minus one c plus c right.
That is equal to NC.
So I'm just splitting it up in this manner now n minus one into C.
Right.
So if the pointer which is over here is doing n minus one cycles it will again reach back over here
wherever it started.
Right.
So it will be back at its initial position when it's doing some number of cycles.
And then the remaining distance that this travels is equal to c minus m.
And we know that c is the distance the length of the cycle.
So c minus m right.
This is c.
And this over here is m is actually if you subtract c minus m that's the distance between this node
and the beginning node.
So that is why we can say that when the head pointer is moving x nodes then the pointer which is at
the meeting point also will move such number of nodes such that both of them is going to be at the node
where the cycle begins.
So that is why we can use this method to find the beginning of the cycle.
That is, the node where the cycle begins.