Hi everyone.
In this video, let's think together how we can solve this question.
Now let's say that the given singly linked list is this one over here.
Now, as mentioned in the question, the input to the function is going to be the head of the singly
linked list.
Right.
So that's this node over here.
Now let's define a variable cur and let's point it to the head of the singly linked list.
Now we will look at the remaining part of the singly linked list.
And let's find the next distinct node.
All right.
So in this case the next node itself is different right.
So distinct means the next node which is different from the current node.
Now remember to remove all the duplicates.
We are trying to remove all the duplicates together as the input is sorted.
Now what do I mean with that?
Let's say we are over here.
Let's say current is over here at some point now we can or we could remove one at a time.
Like when we look at the next node we see we see that it's not distinct.
So we could remove that.
Then again we look at the next one and we could remove that.
We can do that.
We can do it in that way also.
But over here, as the singly linked list over here is sorted, now we can remove all the duplicates
together.
For example, if the input was one pointing to one pointing to one, and that's pointing to, let's
say three, and let's say that points to null.
In this case we could remove one at a time like we current current is pointing over here at the beginning.
Then the next node of uh after this one is a duplicate.
So we could remove it.
Then we again check the next one which is a duplicate.
We remove it and we go on like that.
So that's possible.
But in this approach let's try to find the next distinct node.
So we would go ahead and find that the next distinct node is three in this case.
And then we will remove everything in between together.
So that's how we will approach this because the given singly linked list is sorted.
Right.
So there is no possibility that you'll have one over here, then three over here and then two and then
somewhere over here one.
So this is not possible because it's mentioned that it's sorted.
All right.
So the current variable is pointing to the node where the value is one or the it's the head right.
And after this let's define another variable next distinct and let it point to the next node.
Now we will check whether these two are the same.
Now in this case, these two are the same.
So there's nothing to be.
They are not the same, so there's nothing to be removed.
Therefore, we shift current to the next place.
And when we shift current along with that, in the next step we will also shift next distinct.
So let's do that.
So current shifts over here and over along with that next distinct is the next one after current.
Now in this case we see that these two are the same right.
So instead of removing this at this point we move next distinct one more time.
So we move this one more time.
So it comes over here.
Now we see that these two are not the same right.
So we can remove just whatever comes in between them.
That means we will make this node over here point to this one over here.
So we will make it point to three.
This node will point to three and this connection will be disconnected.
All right.
And for this we will do cur dot next is equal to next distinct right.
So using this operation over here we will make this node point to this one.
And in that way we have removed effectively this node is removed.
All right.
Now once this is done we will again move current to the next node.
And at this point the next node is this one.
Right.
Because this connection over here is severed or it's removed.
So we move current to this place.
And next distinct is the next node.
Right.
And we check whether these two are the same.
Now in this case they are not the same.
So there's nothing to be removed right.
So let me just write the singly linked list one more time below so that it does not get crowded.
Right.
So we have reached till here.
The pointer is at this point over here.
And we've seen that these two that is current and next distinct are different.
So again we move current.
We move current from here to here.
Right.
So current is over here.
And next distinct is the next node which is over here.
Now we compare them.
And at this point we see that they are the same.
So we again move next distinct.
So again it comes over here.
And again we compare these two.
Again they are the same.
Therefore we move next distinct again.
So it comes over here right.
At this point these two are not the same right.
Four and null are not the same.
Therefore we remove everything which is in between.
That means we make this node over here point to next distinct.
So four will point to null and this connection is removed right.
So after this we again move current and current comes to null right.
So when we see that current comes to null in the next iteration, we get the condition to stop the loop.
So we come out of the loop.
And at this point we have removed all the duplicates.
Right.
We have removed this one over here, and we have removed these two over here.
So we have one pointing to two pointing to three pointing to four.
And that points to null.
So there we have our solution.
So what we are doing over here, the interesting part is that we have a pointer.
And then we keep moving.
The next distinct pointer till we get a distinct value.
And if we have let's say two nodes in between over here we have seen that over here.
Right.
We had current over here.
And then we had two nodes.
And after that only we got the next distinct.
So once we find the next distinct we just connect current and next distinct.
And we remove everything which is in between.
Right.
Because this connection is removed and we make this node point to the next distinct node.
So that's how we solve this question.
And the output would be one pointing to two pointing to three pointing to four.
And that points to null.
Now let's quickly look at the complexity of this solution.
The time complexity of this solution is O of n.
Why is that so?
Because we are traversing the singly linked list once right.
So we have we we have seen that initially current was pointing to the head.
And then we kept on moving it right till it reaches over here.
Finally current would be pointing to null.
And it's at that time that we come out of the loop.
So we are traversing the singly linked list once.
Therefore, the time complexity of this solution is O of n.
Now what about the space complexity?
The space complexity of this solution is O of one, or this algorithm runs in constant space because
we are not using any additional space, right?
We are just using pointers and we are just moving the pointers.
So there is no scaling space which we are using.
Right?
And again these nodes are already there in memory.
We are just having pointers to the existing nodes in memory.
So there is no additional space used.
Therefore the space complexity of this solution is O of one.