Hi everyone, I hope you have given it a try to code the solution, which we discussed in the previous
video to reverse a singly linked list.
Now over here, let's go ahead and code it together.
Now I've written a class node and I have made a few nodes over here.
So this is the head node.
It has value one.
And this points to a node with value two.
And this points to a node with value three.
And that points to a node with value four.
Now we are going to write a function.
Let's call this function reverse linked list.
And this function is going to take as input a node which is the head node, and the output will be the
new head node of the reversed singly linked list.
So that's what we're trying to do over here.
Now remember as we discussed in the previous video, the method that we are going to follow is we are
going to have three pointers.
We have one pointer called previous and then we have one pointer called current.
All right.
And we have a pointer called next.
So we are just going to.
Shift the direction in which current points.
Now at this point, current is pointing to next at each uh, of these uh, instances like node one is
the node with value, one is pointing to node with value two.
Node.
Let me just write that over here.
So the node with value one is pointing to the node with value two.
And that's pointing to the node with value three.
And that's pointing to the node with value four.
And that will point to null.
Now we want to reverse this right.
So the output that we want at the end is four which points to three which points to two which points
to one.
And that points to null.
Right.
So we're going to build this step by step.
So initially we'll take this node which is the head node and will make it to point to null.
And then we'll make know the node with value two to point to node one etc..
Right.
So that's the repetitive thing that we're going to do.
And so to remember this just remember that what we are trying to do over here is we are going to change
the direction right.
Currently the current points to next.
And we are going to change this direction.
We'll make current point to previous.
So that's what we are trying to do.
All right.
So if you have this in your mind then you can easily code this.
So let's do it together.
Now over here let me initially have a pointer previous and let it point to null.
All right.
So the value for prev is null.
And let's have current.
And this is set to the input node.
Over here we are given the head.
So we will set this to the head.
And we need a next value right.
Again this will come inside the loop right.
So we'll have a loop.
We'll have a while loop.
And this will go on till there is a current node.
And at each step we will just go to the next value of the current node.
All right.
Now again what will happen.
So we'll have this loop will work when current node is pointing to one.
It will work when it's pointing to two it will work.
When it's pointing to three it will work when it's pointing to four.
But when it's pointing to null, it will break.
So that's what we are accomplishing through this loop.
So we'll just have while current is true right.
And inside this we will find the next value of current.
Now why are we doing this?
Because when we change the direction right over here, we are changing the direction current is pointing
to next.
And we said that our aim is to change the direction in which this points.
Now when we change this, if we don't store the value of next somewhere, then we will lose the connection,
right?
So that's why we need to store next.
And next is equal to current dot next.
So once we have stored the next node then there is no no problem in changing the direction in which
current is pointing.
So we say current dot next is equal to previous.
So we have changed the direction.
So at this point we had one.
So let's just write that over here.
So we changed one.
And now one is pointing to null.
So we have one pointing to null right.
And we have severed this connection.
We don't have this connection anymore.
But there is no problem because we have two stored in next.
Now once we have done this what is it that we need to do?
Remember we are going to shift the position of previous, current and next.
So that's what we that is what we will be doing.
Now.
We just need to in this particular iteration, we just need to shift the position of previous and current
pointers.
And we will find the new next once we come back to this loop again.
So at this point let's set previous to the current value.
So previous is equal to current.
So now we are over here right.
So previous is pointing to one.
And then we need current also to shift right.
So current.
Will point to the next value.
So what have we done over here?
We have made current to two and previous is pointing to one.
So previous is pointing to one and the next of previous is null.
All right.
So we have done this.
And once we have shifted the current pointer now current is over here.
So what happens now current is two current is true.
Again we come over here and we calculate next which is three.
And we change the direction in which current points.
So two dot next right.
So that's equal to one.
So we get two over here.
And that points to two.
And then we change this to previous.
This becomes previous and current becomes three.
Right.
So we again do this.
Now current is now equal to three.
Right.
And we put it over here.
And current becomes four again.
We put it over here and current dot next is null right.
So at this point it's null.
So we break out of this loop.
And all we need to do is we need to return the new head.
And what is the new head at this point the value of current is null right.
We broke out of this while loop because the value of current is null.
But you can see that previous is actually the new linked list which we are building.
Right.
So at this point this four is in previous the node with value four is previous.
So that's the new head.
So we just need to return that.
And we have the solution to our question.
All right.
So let's try and run this and see whether this works.
Now this is the initial uh singly list singly linked list which we have.
So one points to two points to three points to four.
Now let's see let's console log.
What happens when we, uh, pass this singly linked list.
The head of the singly linked list, which initially was there into our function.
All right.
So reverse linked list and we are passing head over here.
Now let's see what it is that we are getting back.
All right, so let me run this.
Now, when we run this, we get this.
So let's see what it is.
So you can see that the value is four which is the last one.
Right.
So this is the value with four is the head now and that's pointing to the node with value three.
And that is pointing to the node with value two.
And that is pointing to the node with value one.
And that in turn is pointing to null.
So yes, we have successfully reversed the linked list right now.
What if only had a single node.
So let's try that.
So let's say that we comment these lines.
So we just have the head one right.
So let's pass it and let's see what we get.
All right.
So again we get a node and we just return that node.
So that's also working.
Now if the input was null what would happen.
Let's try that.
In this case we are just returning null.
So yes our code is working.
It's passing all the test cases right.
So we had a singly linked list in which the first node had a value one, the second had a value two.
Then the third node had a value three and the fourth node had a value four.
And when we pass this over here, we have seen that we got a reversed singly linked list.
Right four three.
And then we have two and we have one.
And that points to null.
So this is working all right.
And you can see that in this function we are just traversing the singly linked list only one time.
Right.
We just traversing it once.
So the time complexity of this solution is O of n.
And the space complexity is O of one.
Because we are not using any extra space, right.
So it's running in constant space.
Therefore the time complexity is O of n and the space complexity is O of one.
Now let's take a relook at the code and let's take a simple test case and walk through it.