Hi everyone.
In this video, let's think through and find a way in which we can solve this question.
Now let's say that this is the input given.
So the input is the head of this singly linked list which is node one.
And that's pointing to node two which is pointing to node three.
And that's pointing to node four.
And that is pointing to null.
Now let's have a pointer.
And let's set the pointer to the input that we received.
Let's call it current.
Or let me just write cur.
All right.
Now before cur we'll have a previous right.
So let's have previous over here.
And initially this points to null because there is nothing over here right now.
Try to visualize what we are trying to achieve right now over here.
If we just take these two right?
Currently one is pointing to two, but in the ideal output in the output that we want.
Let's quickly write that over here, four will be the new head that will point to two.
That will point to three.
Sorry.
That will point to three over here.
This will point to two.
This will point to one.
This will point to null.
Now we can see that in the input one is pointing to two, but in the output we want one to point to
null, right.
So we are actually trying to change the direction in which this point.
So we want this to point in this direction.
Similarly we can see that two is pointing to three right over here.
Oh, so this is four.
This is three.
Two is pointing to one.
All right.
So two is pointing to one.
Now in the input two is pointing to three.
But we want two to point to one.
So we want to change this direction right.
So that's what we want to do.
All right.
So basically if we say that this is next this is current.
And let's say this is next.
Now currently in the input what's happening is current is pointing to next.
But we want to change that and make current point to previous.
So that is basically what we are trying to do.
Now let me make some space over here and clean this up a bit.
Right.
So this is just for our understanding now we have understood that what we are trying to achieve is that
currently current is pointing to next.
We want to change that and make current point to previous.
So this is what we are trying to do.
Now let's think of a method by which we can do this.
All right now.
Over here we have current which is the input.
Let me again repeat.
We have current which is the input.
And we have initialized previous to null.
Now we cannot simply just remove this connection and make one point to null right in the output.
We have seen that one has to point to null, right?
Similarly two has to point to one, etc., right?
So that that was the output that we wanted.
Now we cannot simply disconnect this connection and make the next node of one to be null.
Why is that?
So if we do that, we won't be able to access any of these remaining nodes right?
In the singly linked list, the only way to access the remaining nodes is using the dot next right function.
Right.
So we have to use one dot next to get to this two dot, next to get to this, etc..
Right?
So without storing it we cannot see where this connection.
But at this point we have next over here we have created, we have created a new pointer next and we
have made next point to two.
Right.
So yes, we can access two at this point.
So because we have next, we are in a safe position.
We can disconnect this connection.
Right.
So we are going to remove this connection and we are going to connect it to previous.
So previous is null right.
So we are getting this part over here.
That is one is now pointing to null.
All right.
So we have achieved this much.
Now let me clean this up over here.
Now what we do what we do next is just the repetition of this.
Right.
We are going to move all these three one step ahead.
So what is going to happen is we are going to set previous to current.
So current is one right.
So we are going to set previous to current.
So previous comes over here and we are going to set current to next.
So current will come over here.
All right.
And if current is over here, then next would be the next value, which is over here.
All right.
Now we have current at two previous is this part over here.
And all we need to do is we just need to make this current point to previous again, which is the same
thing that we did over here.
Right.
Again, we need to make this current point to previous.
And we can severe or disconnect this connection.
And that's safe to do because we have stored this over here.
Right.
So we can access the remaining part.
It's not that we are losing the remaining part of the singly linked list.
So we make two point to previous.
Now previous is one and that is pointing to null.
Now when we make two point to previous we get two, one and null right?
So two is pointing to previous.
Now we repeat this whole process again.
We move previous to the next position, we move current to the next position, and when current is in
the next position, next is current dot next.
So that also moves right.
So previous comes to current and current comes to the previous next right.
What was previously next becomes current at this point.
So we move this.
Now what we need to do is we need to store the next value before removing this connection.
We need to store the next node.
So next becomes four.
And after that we can safely disconnect this connection and make current which is three point to previous.
Now when current points to previous, previous is two right and two is pointing to one and one is pointing
to null.
Now current which is three is pointing to previous.
So we get three pointing to two and two points to one.
And that points to null.
So we have got this much right.
And again we repeat the whole process.
We move previous to the next place that is the current over here becomes previous.
So we have previous over here.
And what was next becomes current.
So current is over here right.
And next is the next value after current.
So we get next over here.
So we have these three again.
So next is stored.
So there is no problem in severing this connection even if there was a node over here.
Right.
So again we are we are thinking of a method of doing it right.
So now we have stored whatever is next.
Now we can see we have this connection and we make current point to previous.
So four is pointing to three which is previous.
So four is pointing to three and three is pointing to two, two is pointing to one and one is pointing
to null.
Now at this point again we move it right.
So previous comes over here and current comes over here.
Now current is now pointing to null.
And at this point we can stop the function right.
So we can stop it.
So we can continue our loop through or continue the loop until current is not null, right?
When current is null, we stop and we have our solution.
So that's the way we are going to solve this.
Now this is very easy.
You can easily remember this if you just know that it's this pattern that we are following, right?
Initially we have previous and current.
Now inside the loop we will find next right.
And then we will see where the connection and make current point to previous.
Again we will move previous and current.
We will find next inside the loop.
And we will see where this connection and make current point to previous.
So this is what we have been repeating again and again.
Till current is not equal to null.
When current is equal to null, we are done and we have our solution and we can just return previous,
which is the head of the new singly linked list, which is reversed.
Now that's the solution.
Now let's quickly take a look at the complexity of this solution.
Now the time complexity of this solution is going to be o of n.
Why is that so?
Because we are just traversing the linked list one time right.
We're just traversing it one time.
That's why the time complexity over here is O of n.
Now what about the space complexity?
The space complexity is O of one.
Why is that?
So we are not creating a new linked list, right?
We are just changing the pointers.
Right.
We are just having reference pointers to existing objects in the memory.
So those are these over here reference pointers.
And then we are changing the direction in which particular nodes which are already there in memory are
pointing.
Right.
So we are not using extra space.
So that's why this runs in constant space or O of one.