Hi, everyone.
So today we are going to sign the revised version of the problem that we saw in the earlier session,
so cycle two.
Now, in this problem, what we have to do, so instead of returning a boolean value, we have to return.
The starting point of the loop.
OK, so we have to return to here in the last problem.
We have to return only to our fault.
But in this problem, we have to return the starting point of the loop.
So the starting point of the loop is to OK.
So so this question is present on the record.
OK, so for example, here, the starting point is to set out what should we do here?
The starting point is one or at least the output is one.
And here there is no cycle.
So I will return null.
OK, and our challenge is to solve this problem without using any extra space.
OK.
So this was our only problem.
Now, how we can solve this problem, so the first approach of solving this problem is with the help
of MAP.
OK, we can solve this problem easily with the help of map, just like in the old session, just like
in the earlier session, what we will do, we will take a map of Little North Star and value.
So I will take a map of list North Star and a Boolean value.
So what we will do.
OK, so let's do this problem.
So I have a map, eight percent inside the map.
No one present, no more than nine percent inside the map.
No.
Then Bush for president.
No.
Then put forward to present.
No, but to three percent or seven percent.
No to president no.
Nine percent.
No.
So put all of these.
So three, seven, two and nine.
Then again is to present inside the maps to is present.
So in the only problem would be did the return to at this point.
But here what we will do, we will return to OK, we have I will return my key value, I will simply
return to the time.
Complexity is basically when and the space complexity is on.
OK, so let us implement.
OK, so I closed the solution.
So I will copy the same code just instead of returning the troops, instead of returning to enforce
what they've done.
We will them better than they normally do.
OK, let's make this a.
So instead of returning the true what they will return, I will return, OK, instead of returning false
here, I will return.
OK.
So let's try to separate the so-called.
OK, so our goal is working, so their time in the space complexities both our own.
OK, so can we do better?
Yes, obviously we can do better.
So how we can solve this problem.
So in the earlier session, we we discussed about the floor and the first point, that approach.
OK, so how we can use this law enforcement approach.
So if you remember the legislation both and slow and fast point that approach made at this point.
OK, so both slow and fast point approach, they were meeting at this point.
So after meeting at this point, what I will do, I will find the size of the loop.
OK, so find the size of the loop to her finding the size of the loop.
What what can I do here?
So keep one pointer at three, for example, keep fast pointed at three and move the slow pointer.
OK, so it's lowpoint that will move so slow will come here then slow will come here, then slow will
come here, then snow will come here and then slow will again.
Come here.
OK, so while the slow pointer is moving around, what I will do, I will maintain account and I will
do current placeless.
So when the slope in the first point I will meet again, I will get to know the size of the loop.
OK, so once we know the size of the loop, so let's say the size of the loop.
So here, one, two, three, four and five.
So this is the loop will come out to be five.
OK, so we'll say slope point will come here.
So card will become one, then two, then three, then the will of current forward and then the value
of count will become five.
So we will get to know the size of the loop easily.
Very easily.
OK, so once we know the size of the law, what we can do, we will take two point.
Again, we will take.
Two points again, so I will keep the first pointer here.
And what I will do with the second pointer to the second point, I will move five steps ahead.
So step one, step two, step three, step forward and step five.
So this will be my second pointer.
And then both first and second point, they will move at the same speed.
They will take one jump at a time.
OK, they will take one jump at a time.
So first comes here and second comes here.
First comes here.
Second comes here.
First comes here.
Second comes here.
First comes here.
And second also comes here.
OK, both first and second will meet only at the starting point.
OK, so both first and second pointer, they will meet only at the starting point.
Why starting point.
Because the difference between the second pointer and second pointer minus first point, the difference
between them is basically key and what is fake is basically the size of the loop.
OK, guys, basically the size of the loop, so the only point we had, the first and the second point
I can meet is basically the starting point.
They can they cannot meet anywhere else.
OK, so with the help of this approach, our time will be open and our space will be open.
OK, and this was the challenge.
So in order to write the code.
OK, so far, so what we will do.
We will copy this code also.
Slow and fast pointer approach.
OK, so let's comment about this map approach.
OK, so here we will not return anything, but we will do.
We will only break this loop, OK?
We will only break this loop and this means there is basically cycle cycle addicted.
OK, so the cyclist predicted.
Now, if there is not any cycle, if the cycle is not there, basically if the forest becomes null.
OK, so if the fastest null light means cycle does not exist or we can see the next.
The next of fast becomes then also cycle does not exist.
So if this is the case, that means.
Cycle does not exist, so if the cycle does not exist, we can simply eternal, OK, so there are two
ways to come out of this loop.
First is due to the big statement, that means the news cycle cycle is dead.
Second is with the help of this condition, if this condition becomes false.
So if the condition becomes false, that means there is no cycle.
So I'm returning null, OK?
Now, as discussed, so what we have to do, so I am summarizing the points, what we have to do, we
have to first find the size of the loop.
We have to first find the size of this cycle.
OK, so we're finding the size.
What we do, we will keep the first point where it is and we will move this little pointer around.
And while this low point does meet is moving around, I will maintain the count, OK?
Once we get the count, but we have to do we have to, again, take two pointers.
Both the pointers will be present at the end of the list.
So first pointer and the second pointer will move.
Tekin Pointer count steps ahead.
OK, so count will move.
The second point, the count step ahead.
Now the difference between the second and the first pointer is basically key now both the first and
the second point that they will move at the same speed, OK, they will move at the same speed and the
only point where they can intersect, where they can meet is the starting point of the linked list.
OK, because the difference between them is gay and basically the size of the loop.
OK, so I hope that makes sense to you.
So now let us try to find the size of the loop.
OK, so.
Let's move slow point to one step ahead, so slow because the next Oslo.
OK, and gay kwasman, OK?
Now, while slow, is not close to fast.
But we have to do so slow will move around slow equals next slow.
And we will look, C++ is basically the number of nodes present inside the loop.
OK, now at this point, we know the size of the loop, so I have to take two pointers here.
OK.
So I have to take.
Two pointers, one and two, so they both will be present at the head of the linked list.
OK, they're both fully present at the head of the list.
The second point, the.
Now, what we have to do is move the second point, 30 steps ahead.
OK, so.
Move.
Second point steps ahead.
OK, so while K minus minus.
To is next to.
OK, now what we have to do now move both the point that at the same speed.
OK, so move both first and second pointer at the same speed.
So move both pointer at the same speed.
And they will only intersect at the starting point, so while one is not equal to two.
So what we have to do seems beautiful when it goes the next of one.
And two equals.
Next of the.
OK, so I think our gold is fine and it should work.
OK, so once this loop is over, you can return one or you can return to, OK, I can return one or
I can return to.
OK, so our court is working.
OK, so Al Gore is working now, the time and the space complexity of the solution is time is on and
the space is big of one.
OK, now there is easier way to solve this problem.
OK, we have discussed we have discussed a solution for this problem.
Now there exists a third solution, which is the most optimized solution.
OK, now we will use the floor in the Fassbinder approach.
So if we remember both slow and fast, Pointer will meet here.
OK, so this lowpoint, those here and first point is here now after this low point in the first point,
that approach.
But we have to do.
Move this little pointer at the head of the linked list again.
OK, so remove the slow pointer from here.
And put this low point guard here.
OK, so the first step is move slow pointer to head.
OK, now the second is what will do both slow and fast, move both slow and fast at the same speed?
Move both slow and fast at the same speed.
So what will happen?
So after moving slow and fast, slow will come here.
Fosterville, come here.
Slow welcome here.
Fosterville, come here.
Slow welcome, come here.
Fosterville, come here.
Slow welcome here.
And Fosterville, come here so you can see both slow and fast will meet at the starting point.
OK, so what we have to do, we have to only take two steps.
First, move the slow to the head.
And then move slow and fast at the same speed, and they will intersect at the starting point of the
loop.
Now, why this is the scenario.
So this is very simple mathematical problem.
So first, let us write the code and then we will explain the mathematical solution.
OK.
So let us come out discord.
So what we are doing here?
So this is a simple solution, Fassbinder approach.
OK, so once this low point and the first point I approach, what we have to do is move slow to the
head.
OK, so we have to do two steps.
So the first step is move slow to the head and then move slow and fast at the same speed.
OK.
So move slow to the head, so slow it was a now slow is they're tired and they will only intersect.
At this starting point, so while slow is not too fast.
We have to move them, and this means we at the same speed, OK?
Simple, and you can read Denslow or you can read them first.
OK.
OK, so our goal is working now, we have to write only this much code and we will get the starting
point of the linked list.
Now, how this is working.
Let us try to understand.
OK, so.
So suppose.
This is the cycle in the linked list.
OK, and let's take some variables.
So suppose this is this dense M and let's say this is Mr. Mansky.
And so this is my intersection.
This is basically the starting point of the linked list and this is the point where slow and fast intersect.
OK, initially slow and fast intersect here.
And let's say the size of the slope, the size of this loop is basically let's call it El, OK?
Now, initially, so before meeting at this point, slow and fast pointer.
So how many distance slow points will cover.
So distance traveled by small point.
That is basically this M.
Distance plus, let's say the slope point, I will cover letters lowpoint, I will cover X around,
OK, X complete round of the loop.
So each round is of length L.
So so this low point is covering the x rounds.
Before intersection with the fast pointer.
OK, so it's complete round and each round is of Lendell and then this distance key.
OK, and what is the distance?
So what is the distance travelled by the fast pointer?
So distance traveled by a fast point that is first of all this distance M, so this distance M, let's
say the number of rounds, the first point to go it ottavi.
OK, so while each round is of length L and obviously this distance K OK.
So what are X and why are you so X and Y are basically the rounds?
Of the loop of the cycle before they intersect.
OK.
So so this is the clean bigram.
OK, so this distance from the heart of the link to the starting point, this distances them.
This is key.
This distance is basically key.
Advanced law enforcement intersect and the whole distance, the size of the loop is, well, OK.
So I hope you know the equation.
You know, both these equations will these equations are clear to you?
OK, now one thing that we know, Fassbinder is moving with two x speed, OK?
So if the speed of slow, pointillist X, then the speed of fast point is to X, that means the distance
traveled by a fast pointer is twice the distance travelled by this little pointer.
OK, so in mathematical terms, so distance travelled by a fast pointer is twice the distance traveled
by the slow pointer.
OK, so let's put it all here.
So this is M plus right into L Klasky.
OK, so twice and distance David Westlaw point.
That is M plus X in into L plus K.
OK, so what will happen.
And plus Y into helpless K and multiply to inside so to M plus two excel plus 2k.
OK.
Now, what will happen, so take em decide, take the side and take to excel, decide, OK, so what
will happen?
This will become V minus two.
And 2L is basically.
McCleskey OK, so let me reiterate it.
So basically.
McCleskey.
Is why minus two weeks and total.
OK, and this is our simple diagram.
So this is M and this is K.
OK, so this is.
Now, see, one thing here, emplace gay is an integer, multiple of L.
What is L.
L is basically the size of the loop.
OK, so McCluskey is in danger, multiple of.
Integer, multiple of L.
OK, now can we put one here it is integer multiple.
OK, so why am minus two weeks will be integer.
OK, so it can be anything.
Now suppose it is one.
Suppose it is one.
So basically what I'm writing here K is basically an OK, so suppose this value is one.
This value can be to, this can be three, this value can be anything.
But for the sake of understanding let's suppose this value is one.
OK, so emplace is basically L.
OK, so if this, so this distance is key, that means this distance is M ok because the total distance
is L.
OK, so the total size the loop is.
And so if this much distance is key, if this much distance is K then obviously this will be M.
OK, this is them.
Now see here, so slow and fast pointer, slow and fast.
Both are present at key.
So I am drawing this diagram once again.
This is both slow and fast pointer are presented.
OK, so this distance is key.
This distance is M and similarly, this distance is M.
OK, so both slow and fast pointer are present here.
Now what we did, we moved this slow pointer.
To the head of the linked list, so this is Logan.
Now, what we are doing, we are moving slow and fast at the same speed.
OK, slow and fast are moving at the same speed.
Now, what will happen when slow will cover em distance slow will reach here, slow will reach here
after conveying the distance.
And at the same time, fast will also cover the distance.
M fast will cover the distance and it will also reach here.
And that's how the code will work.
OK, so I hope you understood the code.
OK, so that's how this is working.
If you have any doubt, feel free to ask.
Thank you.