Hi, everyone.
So in today's video, we are going to solve this question, remove get an order from the end of the
linked list.
So let me explain the question and then we will discuss about the possible solution.
So this is these are the notes.
So one, two, three, four, five, six, seven, eight, nine and 10.
So there are total ten nodes, right.
So basically the length of my list is ten.
So this is length of linked list is basically ten.
Right now, what I want to say is so OK, so first let's discuss before moving.
Let us try to find the key.
OK, so if you are able to find the gate and order from the end, then we can also be done with.
So first, let's discuss how we can find a decade or so, for example, let's say the value of KS for.
So what is the fourth node from then.
So this is the first node from the end.
This is the second last note.
This is the third.
And this is the fourth.
So basically, we want to find this node.
OK, after finding this node, we will remove the original question is a removal.
But first, let's discuss how we can find this node.
Right.
So how we can find this node.
So there is one way.
So the first rule is basically it is very simple.
So first, find out the land.
OK, so what is the land?
So Lento's let's say it is.
All right.
So let's say the land is.
And so any number of nodes present in our linked list and so the value of intestine and after finding
out the end.
So and let's say this is key.
So key is basically the key to node from the end.
So get geared node from end is basically and the minus K plus one net node from front.
OK, so let's try to evaluate what I'm saying.
So I want to see that get a note from the end is Samia's and minus K plus one that note from the friend.
OK, so let's see whether whether this formula is basically correct or not.
So this is the fourth node.
OK, so this is the case for.
So this is the fourth node from the end.
So let's apply the formula.
So 10 minus four, plus one.
So this is seven.
So this should be seventh in order from the start.
OK.
So first and second, third, fourth, fifth, sixth and seventh.
So this is seventh in order from the front.
So that means this formula is correct.
So it is the same as get an order from and is same as and minus cabelas when it node from friend.
Now how did I get to this formula.
So basically this simple math formula.
Right.
This is simple math.
Or if you don't know the formula then it is, I mean you can just observe and you can derive this formula.
OK, so this is very simple math.
If you will observe, you can easily reach at this formula.
So how we can find.
So it is very simple.
The first approach says.
So the first approach is step one, find the length of the list.
We know how to find the little interest, just outraged over the compelling encounter.
So after step one, what is step two?
So step two is basically calculate what will calculate.
So you will calculate this value and minus K plus one.
So you know the value of N so and is basically the length to the number of nodes present gains given
by the user.
And so after calculating this formula, let's say the value of KS for and let's consider this example
only and the value of an instant.
So this formula will came out to be seven.
Right.
So how many iterations you want to do so you have to do let's say this value is basically a OK, so
you will do a minus one iterations at minus one iteration.
Basically you will do six jumps.
You will do six jumps.
Let's see, so this is the first to jump.
This is the second jump start to jump forward to jump with the jump and this is the sixth jump.
OK, so we are doing six jumps.
So after doing six jumps, you will reach at this note.
And that's how we will be able to find the node to find the.
So that's how we will be able to find this node.
OK, so in this approach, what is the time, complexity and the space?
Complexity, time?
Complexity is big.
Often we are just finding out the length and iterating over the list again.
Right.
And again, the space complexity is constrained.
We are using constant extra space.
OK, so we are traversing the link list two times.
First, when we are finding out the length.
And second, when we are finding out the node.
So we are doing to travel.
Right.
But the question is, you have to do only one traversal, only one traversal is allowed.
Now the question is, how are we going to solve this question when only one traversal is allowed?
So let's see.
So it is very simple problem, but will do.
So let's take this example, only 10 notes the value of case four.
OK, so we have a..
First, second, third, fourth, fifth, sixth, seventh, eighth, ninth and tenth, so the value
of an assault case for successful means, this is the first word from the end, the second note from
the entire north from the end and the fourth.
Also, I want to find this now.
Right.
OK, so only one traversal is allowed.
We can traverse over the long list only once and not twice.
OK, that means the above approach will not work.
OK, so tell us when the vessel is allowed.
So the approach is basically take two pointers, take two pointers.
So let's call it pointer one.
OK, this is your pointer and this is your pointer to the name.
The name of the first pointer is when the second point is to find.
Now what you will do is basically there's a trick involved here.
So what will the value of KS for?
So maintain the distance between one and two pointer by four.
So that means make to pointer will jump four steps.
OK, so take four steps so two will come here.
First step, second step, third step and fourth step.
So this is your position of two.
So I'm repeating myself again.
So initially when it's presented to you, it's also present at the head.
OK, so initially this is my head of the list.
So when it was present at the head of the linked list, now the value of Gaisford.
So what we will do so take point number two and it will take OK, it will take jumps.
Now, this is to OK, after taking the case for and this is one, how much is the difference between
one and two?
So one, two, three and four.
So the difference between one and two is basically four nodes.
Right?
So the differences for node perfect.
Now, what we will do, so one will move ahead in this direction to really move ahead in this direction.
OK, so this is null.
So the idea is when two will reach at this point.
So when two will reach at null, there will be one president.
So one will present four nodes back.
So that means so first node second or third and fourth.
So one will be present at this node when two will regional.
OK, and one means.
So this is the node that we want to find.
So the steps is very simple.
So what is the first step?
Take two points, one and two.
Initially they will be present at the head.
Now the second step is basically the two pointer will make jumps, the two points will make the jumps.
And now the difference between the pointer to end point seven is basically off key.
Guignard Fine.
Now what we will do so move one and two simultaneously.
One and two will simultaneously move in forward direction rate.
So we have single list.
We can only move forward addiction.
So both will move in the forward direction.
And step number four when two will reach and then so one will reach the node that we want to find basically
the desired node.
So let's take this example only.
So one is here and two is here.
OK, so let's do one thing.
Let's try this let's try this logic on this example.
Right.
So we have 10 nodes.
So this is nor one nor two, three, four, five, six, seven, eight, nine and ten.
And finally, we have nine.
So there is one present, so one and two, initially, they both are retired.
OK, so this is my one and this is my two.
Now two will do jumps and the value of KS for OK, so first to jump, second, jump, jump and fall
to jump.
So this is the position of two.
Fine.
Now both one and two will move forward.
OK, so let's move them forward simultaneously.
So remove the.
So this is OK and remove this will move forward.
So who is moving forward.
One is moving forward.
Who is moving forward?
One is moving forward, two is moving forward and one is moving forward, two is moving forward and
one is moving forward to two regional two is moving forward and one is moving forward.
Now, as soon as your two reaches none.
So one will reach at this node.
And what is this node?
So this is the last node, second or third astronaut and the fourth node from the end.
And this is the node that we want to find out.
OK, so this is our desired node.
So finally went to regional one will be at the desired.
And also finally, what I will do so I will return one.
And via this code is working because the difference between two and one is basically of Kennard's.
So that's why I went to will reach.
The final one will be key nodes behind.
OK, one will be key behind and that's how we will be able to find the gate node from the end and how
much traversal.
So we are doing we are just simply traversing on the link list one time.
OK, so this is only one traversal.
We are not traversing the linked list two times.
We are traversing the linked list only one time.
So again, the time complexity is big off and the space complexity is also big of one.
So space is constrained.
So the time complexity of this matter and the previous matter both has him.
But the only differences we are doing or even traversal in the approach finding out the land approach
there was to traversal.
OK, so here we are using one traversal.
Now let's come back to the original question.
So the original question is not to find out.
The original question is not to find out the gate node from there, and the original question is to
remove the gate and order from then.
OK, so the original question is we have to remove the gate node from then and we have to do this and
one traversal only.
So let's see how we can do this.
So we just have to modify our this approach.
So we just have to modify this approach so how we can modify over this approach.
This is one so one is present at the desired location.
I want to remove this node.
So if you want to delete one node, so suppose this is your linked list.
If you want to delete this node, that means I have to stop at this node.
So I have to stop at this order so that I can do something like this.
Right.
So I have to stop one node before the deciding if this is the node to be deleted.
Then I have to stop one node before the node, which has to delete it.
Right.
So that means we will stop when the reaches.
No, this is not we will stop when he reaches the last node.
These two.
OK, so then two will reach the last node.
So one will be present at this node.
OK, one node behind the note to be deleted and then we can do something like this.
OK, so this node will get deleted.
Right.
So we will just modify this.
So what we have to do so first step will remain same, second step remains same towards the same.
The fourth step will be when two will reach the last node.
And what is the condition of last year or two where next will be null.
So when two will reach the last node, so one will reach one node before the desired node.
So one will reach here.
OK, and then what we can do so we can do one arrow next is basically.
Next of next of kin, right?
We can do we can make this connection right.
So this node will be removed from the linked list.
So we have to modify our solution, right.
OK, so we can do this and we can solve this question in only one traversal.
OK, so similarly, you can update your land approach also.
OK, you can update your land approach.
So what was our land approach?
So Lente approach was first find out the lente, obviously we have to find out the land and then we
have to calculate this Phumla and Mindscape Lasagna's then we were doing AM minus one titrations.
We were doing six jumps to reach the desired node.
So here what we will do instead of five minus one titrations, we will do administrations.
So we will do five jumps so that we can stop one order before the node, which is to be deleted.
We want to delete this not right.
So I will stop at this, at this node and then I will make this connection.
I am minus two iterations so we will do five jumps.
Right.
So you can modify the code.
OK, so let's write the code for removing it from the end of the linked list.
And this is our logic.
OK, so this is our final logic.
Take two points.
One and two waterbird two will make jumps.
One and two will both move in the forward direction.
And this is the stopping right now.
OK, so this is the stopping the idea when the next of two becomes known, that means the last.
And so when will stop one node before the which is related and then we will do this.
OK, so this question is actually present only two, right?
So this is the question.
Remove the net in order from the end of the list and it will see the question.
So it is saying here you have to do this question in one path.
So this one path means only one traversal.
Right.
So we have to do this question one traversal.
OK, so this is the example.
One, two, three, four, five, the value of these two.
So that means I have to remove the node.
So this is the ability link list one, two, three and five.
So instead of let's rename the variable key.
OK, so I want to create a..
So let me write the step so that you can understand what you have to do.
So I will take two pointers.
So pointer one and two initially both represent at the heart of the linked list.
Fine.
So this is step one.
Step two is basically the pointer to will move the jumps.
It will look so that the difference between first and second notice of Gaetjens.
Right.
So the difference between two minus one, this is off key.
Right.
So today's one and two will move in forward direction simultaneously.
So wanting to move forward.
OK, and what is the stopping criteria of moving forward?
So the stopping right is when two will reach the last node.
So we do to add next is basically null.
So when do will reach the last node?
So this is the condition for reaching the last node, then I will stop.
OK, so this is the stopping condition and after that.
So this will be the condition.
OK, so this is one and this is the node which we want to delete.
So I will do I will make a connection like this, so I will do one.
The next one is simply the next of next of one.
And finally, what we will do so if you will see that the function is listed, Alstott, I have to return
the head of the linked list, so finally we will return the head.
OK, so this is our approach.
And the time complexity discussed many times is linear and we are doing only one puzzle when it passes.
So let's see.
Let's write the code.
Right.
So take we have to make two points first.
So Liston would start.
When?
As president and similarly, the second pointed.
You start also this is also President Leithead, OK, so how many jumps he jumps, so we have to do
jumps.
So while guey minus minus so this loop will run good times.
OK, so.
I have to do Ketcham's right?
So this loop will run jumps, so this loop will run.
Sorry, so this Global Times and what we have to do.
So two equals.
Next off, the search is moving forward, correct?
And now one and two will both move forward.
OK, and what is stopping right to do next?
Asmal.
So we have to reach the last 10 or so while to add or next is not a question.
So this is my stomping criteria and both will move forward.
So one equals.
Next up, one and two equals.
Next off, the perfect and finally, so finally, we what we will do, so we will delete it and we will
delete the kid node from end.
OK, so let's delete the node.
So for the leading the node, one arrow next.
Is.
Next off, next of kin.
And after deleting then what we have to do, so I have to return the head of the list, OK, so I have
to return the hair and so I am returning the head.
OK, so I think we did everything fine.
So I think this code should work.
But there is one problem with this code.
So let me run this code and then I will show you what is the problem.
So our is running fine.
But when will submit this?
It will definitely give us a error and I will tell you why that will come.
There is one simple case that we are not considering.
So our court is working.
Yes.
So what we are getting so we are getting runtime error.
OK, so what we are doing here is so this undefined behavior means so this is random, red and white
and tamira you can see.
So this line, what they are doing so you are accessing to do next.
OK, and what if the weasel.
So what if twizzle you are doing null arrow next.
And obviously, this will give you rent, Tamara.
OK, so in what situation this two will be none.
So consider one situation.
So let's say there are five notes in a link list or let's say there are only four notes.
So therefore not in your list.
Right.
And let's say you want to delete the fourth and order from and delete fourth nolde from.
And so this is the first order from the end.
This is the second note from then the third note from then.
And this is the fourth note from then.
So that means I want to delete the first note.
OK, if you apply the formula and minus K plus one so and is for gays also four for minus four plus
one.
So that means the first note from the beginning.
So I want to delete the first note from the beginning and now executable code.
So what we are doing so one and two will put one and two is present here.
So this is your one and this is also your two, right.
Then what you are doing.
So while giving minus minus how many times.
So four times this loop will run.
So one time.
Second time, third time and the fourth time.
So this is.
All right.
So basically your two is pointing towards null.
So your two is pointing towards null and then you are doing null next.
So in this situation, the situation in which the length of the linked list.
So if the length of the list is the same as the then or the value of key, then in that case your two
will become null and you will get married.
Now, how to resolve this problem?
OK.
So think how we can solve this problem, what condition we should add, so we can simply write the condition
here that if basically the pointer too becomes null.
So if BU becomes knowledge that means Gabe becomes equal to the length of the list.
OK, and then in that case what we can do.
So we have to delete that.
OK, so we have to delete the first node.
So in that case we have to delete the first order so we can simply write it down when I do next.
OK, one is pointing towards the first node so we can return one error next.
Fine.
So let's do that.
Let me erase the screen.
OK, so.
Check first that if basically two becomes null if twizzle.
So when this condition will be so, when basically the length of length list is basically close to the
value of.
OK, so in that case, so in that case, what do you have to do?
So you have to delete the head and basically after the first not right.
So for the leading the first nobody can write.
You can write one arrow next.
So we can return when I do next.
OK, so I am returning when I do next door, the function is let's not start.
OK, so now I think our code will work.
OK, so one thing here is so we are not deleting the node.
So our code is basically suffering from memory problem, but that's fine.
Right is fine because we are submitting our code on an online website.
OK, so it's it's ok.
OK, if you want you can handle the memory.
Similarly we have memory like here also.
OK, it's your choice.
If you want to handle the memory leak you can handle.
Otherwise it's also fine.
So let's Amitabha called.
OK, so now this time of accord is working for all the test cases success, and I will call this ninety
two point seven two percent faster than all the zipless resolution.
So that's how our code is working.
And one last time, OK, so we are solving this question in only one hour time.
Complexity is linear and space complexity is constant.
And we are.
And we are solving this question in one post, and you don't need to worry about the value of this,
basically.
OK, so you don't need to worry about gay will always be valid.
So you do not have a conditions like this if gays greater than the length of the list.
So there is no need to write conditions like this because it does give an indication that the case is
going to be valid.
So if I have any doubt in this question, you can ask me.
OK, thank you.