Hi everyone, I hope you have given it a try to code the solution which we discussed in the previous
video.
Now in this video, let's code it together.
Now before we start and create a function to remove the duplicates over here I have created a singly
linked list.
Now this is not part of the solution.
This is just to be able to test the function once we have written it.
So I have class node and it has a constructor.
So whenever a node is created a value has to be passed.
And this dot val is set to the value which is passed.
And this dot next that is that particular node is pointing to null.
So that's the class over here and the constructor over here.
And using this class node I've created node one.
So there is a node with value one.
And we call it head.
And that node points to a node with value two.
And that points to another node with value two.
All right.
So I've just roughly drawn it out over here.
And that points to another node with value three.
And again that points to another node with a value where the character a.
And then that points to a node with a value character a.
Now this is the singly linked list which we have.
Now once we write the function and when we pass the head to that function, we should be able to remove
the nodes with duplicate values and then give back the head.
So that's the question.
So let's start writing our function.
Let's call the function remove dupes.
Okay.
And this function takes in a node as input.
So let's just call it head.
Now first let's have a pointer.
Let's call it cur.
And let's let let's make it point to the head in the beginning.
Now we will have to iterate through the given singly list ones.
Now to know that we can stop.
So at the end.
Right.
So this one over here will be pointing to null, right.
The end of the singly linked list will be pointing to null.
So we will keep moving current from left to right.
And we will stop when current is null right.
So when current is null or cur, in this case cur is null, we will know that we have reached the end
of the singly linked list.
So let's have a while loop.
So this will keep going on till current is truthy.
Right now when current is null, it will become falsy and we will come out of the while loop.
All right, so we have a while loop for that.
Now what we do is once we are inside the while loop, let's have another pointer and let's call it um
next distinct value.
Or next, next distinct.
Well, and this one is going to point to the next node, the immediate node after cur or current.
All right.
So this is just short form for current.
So next distinct val is equal to cur dot.
Next.
All right.
Now we are going to check whether that value and the current value is the same.
Now if they are the same then we need to check when the next distinct value happens.
For example let's say current was at two.
So next distinct value as per this will be over here right at the next node.
Now these are the same now as we saw in the previous video.
We need to again move the next distinct value till we get to a value which is different from the current
node, so that we can connect those two.
Right.
So again we don't know how many times we would need to move forward.
Right.
We could have a singly linked list where one is pointing to two.
And that's again pointing to two.
And then let's say it's pointing to five.
So we need to know that, uh, let's say we are at two.
Then the next two nodes is two.
So we need to keep going till we find five so that we can connect to and five.
So for this again we will have a while loop.
Now we will keep doing this till current dot val.
Is equal to next distinct dot val.
All right.
Now, there is one thing that you need to take care over here.
Now, if you keep doing.
And again what?
Let's just write it out so that you can understand.
Inside this, what we will be doing is we will be shifting the position of next distinct.
Well right.
So next distinct val is equal to next distinct val dot next.
That's what we will be doing inside this while loop.
Now just imagine what happens when at some point let's say next distinct val is at the end over here.
Right.
For example, the case that we have over here, right.
Let's say current is pointing to this node over here.
And next distinct wall is over here.
So they are equal.
So we come inside the while loop and we will again move next distinct val forward as per what we've
written over here.
Right.
So in that case next distinct wall will point to null right.
So we want to avoid that because if you don't avoid that what will happen is again we will compare this
node and null and they are not equal.
So we will come again inside the while loop.
But then over here we will get an error.
Next next distinct val dot next right.
It's already at null and this is not pointing anywhere else.
So this will not work.
So we need to avoid that case.
For this we need to ensure one more check.
We need to ensure that next distinct val is not equal to null.
So let's add that over here.
So now it will work.
So when we come out of the while loop over here, we will have a distinct val over here.
Right?
So the value at cur and the value at next distinct val will be different.
Right.
So all we need to do is we need to connect them so we can say cur dot next is equal to.
Next distinct wall.
All right.
So we can connect them.
And then we just need to move her to the next position.
So Cur is equal to next distinct wall.
So that's the next position at this point.
Right.
Because we have connected these two.
So after cur we get next distinct wall.
So we just set cur to next distinct wall.
Now if cur is not null this loop will repeat again.
And once we are out of this loop, we can be sure that all the duplicates in the given singly linked
list is are removed.
And we can just return the head and we can see that the duplicates are removed.
All right.
Now let's go ahead and run the function that we have created and let's see what output we get.
All right.
So I'm initially let me just run it.
And I could either call the function over here itself or we can do it in the console this time.
Let's do it in the console.
So let me run it over here.
And now I have not called the function right.
So let's see if I just take head.
What what is the singly linked list looking like.
Let's take a look at it.
So let me just make this bigger.
So the initial value is one.
Now you can see that it's pointing to two.
That's again pointing to two.
Right.
And that is pointing to three which is pointing to a which is a character.
And that's pointing to a.
And then uh, that's the end.
Right.
And then it's pointing to null.
So 1223A and A.
So this is the singly linked list which we have now.
Now let's call the function remove dupes which we have written.
And let's pass the head to this function.
All right.
So we have done that.
Now let's look at what the singly linked list look like.
Right.
So we have the head.
So again let me open it up.
Now you can see that one is pointing to two.
Two is pointing to three, and three is pointing to a, and that's pointing to null.
So you can see that the duplicates have been removed.
And our function is working.
Now over here.
Notice that the time complexity of this solution is just O of n, because we are just traversing the
singly linked list one time and we are not using any extra space.
So the space complexity of this solution is O of one.
Now let's take a sample input and quickly look at what's happening at different stages in our code.