1
00:00:00,760 --> 00:00:05,950
Hi everyone, I hope you have given it a try to code the solution which we discussed in the previous

2
00:00:05,950 --> 00:00:06,580
video.

3
00:00:06,580 --> 00:00:09,280
Now in this video, let's code it together.

4
00:00:09,280 --> 00:00:15,160
Now before we start and create a function to remove the duplicates over here I have created a singly

5
00:00:15,160 --> 00:00:15,880
linked list.

6
00:00:15,880 --> 00:00:17,680
Now this is not part of the solution.

7
00:00:17,680 --> 00:00:21,430
This is just to be able to test the function once we have written it.

8
00:00:21,430 --> 00:00:24,520
So I have class node and it has a constructor.

9
00:00:24,520 --> 00:00:28,360
So whenever a node is created a value has to be passed.

10
00:00:28,360 --> 00:00:31,690
And this dot val is set to the value which is passed.

11
00:00:31,690 --> 00:00:36,670
And this dot next that is that particular node is pointing to null.

12
00:00:36,670 --> 00:00:39,730
So that's the class over here and the constructor over here.

13
00:00:39,730 --> 00:00:43,000
And using this class node I've created node one.

14
00:00:43,000 --> 00:00:44,740
So there is a node with value one.

15
00:00:44,740 --> 00:00:45,850
And we call it head.

16
00:00:45,850 --> 00:00:49,060
And that node points to a node with value two.

17
00:00:49,060 --> 00:00:51,940
And that points to another node with value two.

18
00:00:51,970 --> 00:00:52,270
All right.

19
00:00:52,270 --> 00:00:54,910
So I've just roughly drawn it out over here.

20
00:00:54,910 --> 00:00:57,370
And that points to another node with value three.

21
00:00:57,370 --> 00:01:02,620
And again that points to another node with a value where the character a.

22
00:01:02,620 --> 00:01:05,770
And then that points to a node with a value character a.

23
00:01:05,800 --> 00:01:09,010
Now this is the singly linked list which we have.

24
00:01:09,010 --> 00:01:14,770
Now once we write the function and when we pass the head to that function, we should be able to remove

25
00:01:14,770 --> 00:01:18,160
the nodes with duplicate values and then give back the head.

26
00:01:18,160 --> 00:01:19,180
So that's the question.

27
00:01:19,180 --> 00:01:21,670
So let's start writing our function.

28
00:01:21,670 --> 00:01:24,640
Let's call the function remove dupes.

29
00:01:27,300 --> 00:01:27,900
Okay.

30
00:01:27,900 --> 00:01:31,170
And this function takes in a node as input.

31
00:01:31,170 --> 00:01:32,670
So let's just call it head.

32
00:01:32,700 --> 00:01:36,510
Now first let's have a pointer.

33
00:01:36,510 --> 00:01:37,650
Let's call it cur.

34
00:01:38,040 --> 00:01:41,670
And let's let let's make it point to the head in the beginning.

35
00:01:42,330 --> 00:01:47,610
Now we will have to iterate through the given singly list ones.

36
00:01:47,640 --> 00:01:49,680
Now to know that we can stop.

37
00:01:49,680 --> 00:01:50,610
So at the end.

38
00:01:50,610 --> 00:01:50,850
Right.

39
00:01:50,850 --> 00:01:53,760
So this one over here will be pointing to null, right.

40
00:01:53,760 --> 00:01:56,880
The end of the singly linked list will be pointing to null.

41
00:01:56,880 --> 00:02:00,450
So we will keep moving current from left to right.

42
00:02:00,450 --> 00:02:02,970
And we will stop when current is null right.

43
00:02:02,970 --> 00:02:08,280
So when current is null or cur, in this case cur is null, we will know that we have reached the end

44
00:02:08,280 --> 00:02:09,510
of the singly linked list.

45
00:02:09,510 --> 00:02:11,280
So let's have a while loop.

46
00:02:11,280 --> 00:02:16,200
So this will keep going on till current is truthy.

47
00:02:16,230 --> 00:02:21,630
Right now when current is null, it will become falsy and we will come out of the while loop.

48
00:02:21,630 --> 00:02:23,820
All right, so we have a while loop for that.

49
00:02:23,820 --> 00:02:30,600
Now what we do is once we are inside the while loop, let's have another pointer and let's call it um

50
00:02:30,600 --> 00:02:33,180
next distinct value.

51
00:02:35,320 --> 00:02:36,730
Or next, next distinct.

52
00:02:36,730 --> 00:02:43,750
Well, and this one is going to point to the next node, the immediate node after cur or current.

53
00:02:43,750 --> 00:02:44,050
All right.

54
00:02:44,050 --> 00:02:46,090
So this is just short form for current.

55
00:02:46,090 --> 00:02:49,390
So next distinct val is equal to cur dot.

56
00:02:49,390 --> 00:02:50,050
Next.

57
00:02:50,050 --> 00:02:50,800
All right.

58
00:02:50,800 --> 00:02:56,560
Now we are going to check whether that value and the current value is the same.

59
00:02:56,560 --> 00:03:02,050
Now if they are the same then we need to check when the next distinct value happens.

60
00:03:02,050 --> 00:03:04,540
For example let's say current was at two.

61
00:03:04,570 --> 00:03:09,190
So next distinct value as per this will be over here right at the next node.

62
00:03:09,190 --> 00:03:12,130
Now these are the same now as we saw in the previous video.

63
00:03:12,130 --> 00:03:17,680
We need to again move the next distinct value till we get to a value which is different from the current

64
00:03:17,680 --> 00:03:19,420
node, so that we can connect those two.

65
00:03:19,420 --> 00:03:19,780
Right.

66
00:03:19,780 --> 00:03:22,840
So again we don't know how many times we would need to move forward.

67
00:03:22,840 --> 00:03:23,230
Right.

68
00:03:23,230 --> 00:03:26,380
We could have a singly linked list where one is pointing to two.

69
00:03:26,380 --> 00:03:27,940
And that's again pointing to two.

70
00:03:27,940 --> 00:03:29,530
And that's again pointing to two.

71
00:03:29,530 --> 00:03:31,840
And then let's say it's pointing to five.

72
00:03:31,840 --> 00:03:35,800
So we need to know that, uh, let's say we are at two.

73
00:03:35,800 --> 00:03:37,900
Then the next two nodes is two.

74
00:03:37,930 --> 00:03:42,010
So we need to keep going till we find five so that we can connect to and five.

75
00:03:42,010 --> 00:03:44,740
So for this again we will have a while loop.

76
00:03:45,340 --> 00:03:49,150
Now we will keep doing this till current dot val.

77
00:03:50,110 --> 00:03:53,140
Is equal to next distinct dot val.

78
00:03:56,030 --> 00:03:56,510
All right.

79
00:03:56,510 --> 00:04:00,200
Now, there is one thing that you need to take care over here.

80
00:04:00,230 --> 00:04:01,700
Now, if you keep doing.

81
00:04:01,700 --> 00:04:02,390
And again what?

82
00:04:02,510 --> 00:04:04,520
Let's just write it out so that you can understand.

83
00:04:04,520 --> 00:04:09,350
Inside this, what we will be doing is we will be shifting the position of next distinct.

84
00:04:09,350 --> 00:04:09,860
Well right.

85
00:04:09,860 --> 00:04:14,750
So next distinct val is equal to next distinct val dot next.

86
00:04:14,810 --> 00:04:17,480
That's what we will be doing inside this while loop.

87
00:04:17,480 --> 00:04:24,260
Now just imagine what happens when at some point let's say next distinct val is at the end over here.

88
00:04:24,260 --> 00:04:24,740
Right.

89
00:04:24,920 --> 00:04:27,890
For example, the case that we have over here, right.

90
00:04:27,890 --> 00:04:31,130
Let's say current is pointing to this node over here.

91
00:04:31,130 --> 00:04:33,260
And next distinct wall is over here.

92
00:04:33,260 --> 00:04:34,640
So they are equal.

93
00:04:34,640 --> 00:04:40,010
So we come inside the while loop and we will again move next distinct val forward as per what we've

94
00:04:40,010 --> 00:04:40,520
written over here.

95
00:04:40,520 --> 00:04:40,820
Right.

96
00:04:40,820 --> 00:04:44,630
So in that case next distinct wall will point to null right.

97
00:04:44,630 --> 00:04:50,450
So we want to avoid that because if you don't avoid that what will happen is again we will compare this

98
00:04:50,450 --> 00:04:52,610
node and null and they are not equal.

99
00:04:52,610 --> 00:04:54,830
So we will come again inside the while loop.

100
00:04:54,830 --> 00:04:56,690
But then over here we will get an error.

101
00:04:56,690 --> 00:04:58,760
Next next distinct val dot next right.

102
00:04:58,760 --> 00:05:01,910
It's already at null and this is not pointing anywhere else.

103
00:05:01,910 --> 00:05:02,990
So this will not work.

104
00:05:02,990 --> 00:05:05,090
So we need to avoid that case.

105
00:05:05,090 --> 00:05:07,850
For this we need to ensure one more check.

106
00:05:07,850 --> 00:05:12,680
We need to ensure that next distinct val is not equal to null.

107
00:05:12,680 --> 00:05:14,390
So let's add that over here.

108
00:05:16,070 --> 00:05:17,720
So now it will work.

109
00:05:17,720 --> 00:05:23,300
So when we come out of the while loop over here, we will have a distinct val over here.

110
00:05:23,300 --> 00:05:23,480
Right?

111
00:05:23,480 --> 00:05:27,830
So the value at cur and the value at next distinct val will be different.

112
00:05:27,830 --> 00:05:28,220
Right.

113
00:05:28,220 --> 00:05:34,190
So all we need to do is we need to connect them so we can say cur dot next is equal to.

114
00:05:35,550 --> 00:05:36,900
Next distinct wall.

115
00:05:38,780 --> 00:05:39,080
All right.

116
00:05:39,080 --> 00:05:40,130
So we can connect them.

117
00:05:40,130 --> 00:05:43,340
And then we just need to move her to the next position.

118
00:05:43,340 --> 00:05:45,470
So Cur is equal to next distinct wall.

119
00:05:45,470 --> 00:05:47,030
So that's the next position at this point.

120
00:05:47,030 --> 00:05:47,390
Right.

121
00:05:47,390 --> 00:05:49,070
Because we have connected these two.

122
00:05:49,070 --> 00:05:52,400
So after cur we get next distinct wall.

123
00:05:52,400 --> 00:05:55,430
So we just set cur to next distinct wall.

124
00:05:55,430 --> 00:05:59,090
Now if cur is not null this loop will repeat again.

125
00:05:59,090 --> 00:06:05,780
And once we are out of this loop, we can be sure that all the duplicates in the given singly linked

126
00:06:05,780 --> 00:06:07,520
list is are removed.

127
00:06:07,520 --> 00:06:12,980
And we can just return the head and we can see that the duplicates are removed.

128
00:06:12,980 --> 00:06:13,460
All right.

129
00:06:13,490 --> 00:06:19,730
Now let's go ahead and run the function that we have created and let's see what output we get.

130
00:06:21,150 --> 00:06:21,540
All right.

131
00:06:21,540 --> 00:06:24,060
So I'm initially let me just run it.

132
00:06:24,060 --> 00:06:29,700
And I could either call the function over here itself or we can do it in the console this time.

133
00:06:29,700 --> 00:06:30,990
Let's do it in the console.

134
00:06:30,990 --> 00:06:32,670
So let me run it over here.

135
00:06:32,670 --> 00:06:35,970
And now I have not called the function right.

136
00:06:35,970 --> 00:06:38,640
So let's see if I just take head.

137
00:06:38,640 --> 00:06:41,610
What what is the singly linked list looking like.

138
00:06:41,610 --> 00:06:42,930
Let's take a look at it.

139
00:06:42,930 --> 00:06:44,640
So let me just make this bigger.

140
00:06:44,640 --> 00:06:46,590
So the initial value is one.

141
00:06:46,590 --> 00:06:48,630
Now you can see that it's pointing to two.

142
00:06:48,660 --> 00:06:50,550
That's again pointing to two.

143
00:06:50,550 --> 00:06:50,970
Right.

144
00:06:50,970 --> 00:06:55,560
And that is pointing to three which is pointing to a which is a character.

145
00:06:55,560 --> 00:06:57,060
And that's pointing to a.

146
00:06:57,060 --> 00:06:59,460
And then uh, that's the end.

147
00:06:59,460 --> 00:06:59,670
Right.

148
00:06:59,670 --> 00:07:00,780
And then it's pointing to null.

149
00:07:00,780 --> 00:07:03,510
So 1223A and A.

150
00:07:03,540 --> 00:07:06,210
So this is the singly linked list which we have now.

151
00:07:06,210 --> 00:07:09,900
Now let's call the function remove dupes which we have written.

152
00:07:09,900 --> 00:07:14,190
And let's pass the head to this function.

153
00:07:14,610 --> 00:07:15,060
All right.

154
00:07:15,060 --> 00:07:16,050
So we have done that.

155
00:07:16,050 --> 00:07:19,950
Now let's look at what the singly linked list look like.

156
00:07:19,950 --> 00:07:20,280
Right.

157
00:07:20,280 --> 00:07:21,450
So we have the head.

158
00:07:21,450 --> 00:07:23,250
So again let me open it up.

159
00:07:24,320 --> 00:07:27,230
Now you can see that one is pointing to two.

160
00:07:27,260 --> 00:07:31,610
Two is pointing to three, and three is pointing to a, and that's pointing to null.

161
00:07:31,610 --> 00:07:34,550
So you can see that the duplicates have been removed.

162
00:07:34,550 --> 00:07:36,830
And our function is working.

163
00:07:36,830 --> 00:07:37,580
Now over here.

164
00:07:37,580 --> 00:07:43,220
Notice that the time complexity of this solution is just O of n, because we are just traversing the

165
00:07:43,220 --> 00:07:47,150
singly linked list one time and we are not using any extra space.

166
00:07:47,150 --> 00:07:50,120
So the space complexity of this solution is O of one.

167
00:07:50,120 --> 00:07:56,960
Now let's take a sample input and quickly look at what's happening at different stages in our code.