Hi, everyone.
So in today's video, we are going to solve this question and find the midpoint of a long list.
OK, so one link left.
Let's say the linked list is of Aadland.
So one, two and three, four and five.
OK, so what is the midpoint?
So my point is basically this node three.
OK, so what?
We have to return.
The return of the function will be node star.
And let's say the name of the function is find out what it will take.
So it will take had input.
OK, so we have to write the code.
In this case when the Linklaters of all and then three, the middle node.
So I have to return the node three right now.
Let's consider this case when the length is basically even so one, two, three, four, five and six.
So in this case basically the length is even so there are two, three and four.
So two me are there now out of these two.
I have to return the second.
OK, so I have to return the second node.
So I have to return for.
So I hope you understood the question.
Now let's see how we can solve this question.
So first way of solving this question is basically first find out the length of the linked list.
OK, so in this case, what is the length of the list five?
In this case, what is the length of the six?
OK, so first step is done now in the second step, what we will do.
So you will do length by two, you will do length by two.
So five by two is basically integer, one integer is basically two.
And similarly what is six by two is three.
Right.
So this is index zero, index one, index two and three and index four.
Now the third step is basically iterate how many times leant upon two times.
So you can see lent by two is two and you can see.
So the node three is present at index also first and second iteration.
So you have to add rate length by two number of times.
Simple, right.
And in this case also lent about two was three and you can say zero.
You can see zero, one, two and three.
So the node for its present at the the N-word is index three.
So index three is basically linked by two.
So we have divided three times one time, a second time and basically third time.
Right.
So we can solve this question by finding out the length.
Then we will do length by two and then we will get that much number of times simple now.
So basically we are traversing the linked list two times, so we are traversing the linked list two
times.
So first time we will traverse to find out the length.
Right.
And the second time we will traverse the linked list to find out the middle element and we will do length
by two.
OK, we related leant upon two times.
So if I will use this approach, finding the length first and then finding out the middle element.
So I am traversing the list two times.
OK, so I hope you understood what is the meaning of two times or two times.
What I want to say is first of all, you have to find the length, right?
First of all, you have to find the length.
That means you will I draw the link list.
So this is one traversal now, the second time you will like trade over the link list and length by
two number of times.
So this is your second traversal.
So that is the meaning of two traversal.
OK, so this is we are travelling two times.
But the question is, let's say the question is find the midpoint of the linked list in one traversal
in only a single one traversal.
OK, we cannot traverse the list two times.
We have to traverse the link list only once and then find out the better part of the linked list.
So can you solve this question?
So it's very easy.
So this approach and the approach is called slow and fast pointer approach, slow and fast pointer approach.
Now, what this approach says is basically so consider or lengthening list one, two, three, four
and five.
OK, and we will also consider even lengthening list one, then two, three, four, five and six.
So what is slow and fast pointer approach?
So it is a very simple approach.
It is a slow pointer at the hard and fast pointer next offered OK and similarly slow pointer initially
slow pointer will be present at the hard and fast pointer will be presented next of.
OK, so first step is basically initialization.
Now this approach is slow pointer will make will take a jump of one and fast pointer will take two jumps.
OK, so what is the meaning.
So I want to say slow will take a jump of one.
So slow equals next of slow and fast will take a jump of two.
So fast equals next of next of fast.
OK, so the logic is slow.
Will take a jump of one correct and fast will take a jump of two.
So this is taking a jump of one and this is taking a jump of two.
So the logic is so finally we have Nele here and finally we have Nele here.
So the logic, the main idea behind this approach is basically when fast reaches none.
OK, so when Fosterville Regional, then basically Uslu will be present at mid.
OK, understood.
So this is the core idea of this approach.
So what is the idea?
So you have to point us slow and fast.
Fast is taking a jump off too slow is taking a jump of one then basically when.
Fosterville reach the end of the limitlessness only means the end of the list, then basically global
reach at the middle of the list, right.
It is very obvious, right?
Fastest moving twice the speed of slow.
OK, so the fast speed is twice the speed of a slow.
So fast is moving with quite the speed of slow, two times the speed of slow.
So it is obvious when Fosterville reach the end of the linked list.
This is the end of the list.
Then slow pointer will reach the middle of the list.
So let's see how.
OK, so Slovik, take a jump of one.
Oslo is here, and it simultaneously forced you to jump off to so fast, takes a jump off to.
Now, again, snow takes a jump of one, so snow takes a jump of one, and Fosterville take a jump of
two so fast takes a jump of two.
Now you can see when fast reaches nul, then very slow.
So your slow is present at the midpoint of the enclosed right slow, especially at the midpoint of the
lift.
Now let's consider even case also.
OK, let's consider even case so slow takes a jump of one.
So this is your slow and fast will take a jump of two at the same time.
OK, so this is at the same time simultaneously and fast jump so fast we'll reach here.
Simple.
Now a slow takes a jump of one.
OK, so this is my slow and fast take the jump off to.
OK, so this is your first.
Now, one thing to observe here is can fast take two jumps now.
No, it is not possible.
It is not possible because the next fastest.
OK, so here we cannot take two jumps and why we cannot take two jumps because fast or next.
So this part is null.
And I told you what is the rule.
So whenever you have something and after that you have next.
That means this thing should exist.
And if this thing does not exist, then basically you will get a random error.
OK, so this thing cannot be this thing cannot win an otherwise you will get married.
Now if you will see carefully.
So the next of fast is basically nil.
So I can not take two jumps.
That means I have to stop here.
I have to stop here.
So if I'm stopping here, check slow, slow, slow is at three and three is not actually the end for
both Halmet.
But I have discussed above that we have to return.
OK, we have to return second made and not the first bit.
So what we will return.
We will return slower or next.
Simple, right.
So what is slow.
Slow is basically this law and what is slower next.
And this is basically this not OK, simple.
So that's how it is working now.
Final rule, OK.
So one last time discussion.
So in case of old it is very simple then fast in case of fast will become fast will become null and
you will simply return slow.
It will simply slow.
You can see so this fast, this fast actually becomes null.
And this is your solution which is at the midpoint.
Now in case of even it is a little bit different, fast will not become null.
In fact, the next of fast is becoming well.
OK, you can see.
So this is your first.
So the next hour fast is becoming null.
And that case you can do Denslow, but in the end it is saying that you have to return the second and
not the first.
OK, so for returning the second limit, I have to return slower next.
OK, simple.
Fine, and initially we know initially, so this will be my slow and fast will be the slow will be ahead
and fast will be headed next.
OK, so this is next.
And I hope you understood the question.
Now, this requires only one traversal.
So let me write the call and then I will show you.
OK, so this question is basically present.
Don't let go.
OK, so this question is present only today and we will write the code here.
So we have the written list not start.
OK, so the name of the function is Matalote and we are receiving as input.
And if you read the question, the question is, so if there are two middle nodes, then you have to
return the second model.
OK, fine.
So as discussed.
So what we discussed.
So I told you, if you have a long list to one, two, three and five, so I'm taking two pointers initially,
this will be my solo and this will be my first.
And in case of forward, what will happen so your fast becomes null and you will Denselow.
In case of even the next of fast becomes null and according to the question, you have to return.
The next off slow, OK, so slow arrow next you can see so you can we have to return the second model
symbol, right?
So now let us write the code.
So let's stick to Pointer North Star, slow, slow is presented, OK, initialization and very fast
present.
So fast is president at the next office.
OK, so you can see slow is initially here and fast is here.
So now we have to do so.
We have to hydrate.
So while fast is not to cause trouble, but you have to also.
Right the next hour, fast is also not because fast is going to make two jumps.
OK, so if this condition is too slow, takes a jump of one, so slow equals next slow and fast takes
a jump of two.
So fast equals.
Next of next hour, fast, simple, right, when you will come out of this very loop.
So there are two ways of coming out of this loop.
Either the fast will become known or the fast growing next will become known.
OK, so if basically.
If fast around external.
Or you can say so if fast exist.
OK, let me write like this.
So if faster than external, that means
so that means basically you have equivalent, right.
So if you have even learned what you will return, it will return slower next.
Otherwise, what you will have done, you will return slow in case of.
OK.
So this is in case of hard.
So I think this is pretty much that we have to do.
So let's see how it is working.
So this is I told you, this is the initial step again, the initialization step.
OK, fine.
And see, I told you, whenever you are putting next in ahead of something, then basically that thing
should exist right.
So fast.
Next should exist.
So that's why I wrote this condition.
OK, and should exist because you are putting next in front of us.
So that's why this condition and obviously we have to choose and operator simple right now, when you
will come out of this, why loop.
So either you have our lengthening list or do you have event linked list.
So if you have even lengthening list, then basically this is the condition.
So I am checking if the next of fastest and then yes, it is then basically as decided we have to return
this next.
So we are returning the extra flow and in case of Ford, you will simply return slow.
So that's why I'm returning slow in case of Aadland linked list.
So you can see here this is only one traversal.
So we are traversing the linked list only once.
We are traversing the linked list only once.
OK, so we are doing single traversal to find out the middle order in our previous approach.
First we were finding the length and for finding the length of one traversal and for finding the middle
road we have to do we have to iterate at length about two times to find out the middle road.
OK, so there was two traversal.
Now this is one traversal.
So which one is better?
This approach, this slow and fast pointer approach, so slow and fast pointer approach is very good.
OK, so this is better than this approach.
All the time complexities seem right.
So time complexity in both cases that big often.
But in this approach we have one traversal.
In this approach we have to traversal and law enforcement approach is very important and it is used
in many places.
So the logic was very simple.
I am repeating myself fast is moving two times the speed of slow.
So when fast will reach the end of the list, then slow will basically reach the middle of the list.
And that is the logic behind this approach.
So now let us test our solution with our solution is basically correct or not.
So let me test our solution.
So one thing that we did wrong here is basically we are using Nolde and you will see the structure.
So we have listner, OK, and we have to return restored and not in order.
So let's replace this.
This is not the civil list.
OK, so this will be listner and I think so this is held right.
OK.
OK, yeah.
So first we will run this code and then we will submit.
OK, so first run code.
So we are getting an error here, OK?
So can you guess why we are getting an error here?
So it's very simple.
I did a very silly mistake.
So what we are doing here, we are using we are writing fast eru next.
OK, so at this time we are writing faster.
Now what if fast isn't a.
OK, so what the fastest then we are, we will get a right.
So instead of taking fast next, we're going to begin simply check if fast exist, we can simply check
it first exist.
So let me do that.
So instead of writing this condition, you can simply write it first exist, so if that means this is
even and I can assure you see in this case, in case of.
So in case of Ford fast becomes.
That means in case of even fast will not be.
OK, so in case of even fast is not only.
Simple, right?
So I'm using this condition in case of even faster, not so in case of even fast exist how to use this
line if fast exist or you can simply ride like this.
So if fast is not questionable, voters seem OK now.
Rancourt again.
OK, so accepted.
So this was the input provided by the this website and I would expect it out.
This is our output three, four, five, and this is the expected output, three, four, five.
And how this is the expected output, because what it is doing here is we are returning the middle order.
So we turning three and this in the back end of late.
So what they are doing, they are printing everything starting from the middle to the end.
So they are printing three, four, five.
And the expected output was also three, four, five.
OK, so that's how it is working.
So after I accepted, now we will submit our code and let's see whether our code is correct or not.
So let's meet our code.
So here you will see the solution.
OK, so success means our goal is working and our goal is basically faster than a hundred percent of
the C++ submission made for this question list.
OK, so I will share this quote with you.
So if you have any doubt in this question, you can ask me.
OK, thank you.