1
00:00:00,730 --> 00:00:01,690
Welcome back.

2
00:00:01,690 --> 00:00:06,160
Let's now go ahead and code the solution which we discussed in the previous video.

3
00:00:06,160 --> 00:00:09,670
Now over here I have a class node with which I will make the notes.

4
00:00:09,670 --> 00:00:10,090
All right.

5
00:00:10,090 --> 00:00:12,070
And then we have the class linked list.

6
00:00:12,070 --> 00:00:17,590
And over here I've included the added tail function which we have discussed in the construction video

7
00:00:17,590 --> 00:00:18,880
for the singly linked list.

8
00:00:18,880 --> 00:00:22,210
Now we will use this over here to make two linked lists.

9
00:00:22,210 --> 00:00:26,620
So let's try 540 plus 723 once we have written the function.

10
00:00:26,620 --> 00:00:32,170
So to test our code, once we have written the function over here I have made a linked list n1.

11
00:00:32,170 --> 00:00:38,380
And over here you can see that you have uh zero pointing to four pointing to five because we are adding

12
00:00:38,380 --> 00:00:39,010
at the tail.

13
00:00:39,010 --> 00:00:42,070
And then you have three pointing to two pointing to seven over here.

14
00:00:42,070 --> 00:00:44,800
Now we are going to use these two to test our code.

15
00:00:44,800 --> 00:00:46,030
So let's get started.

16
00:00:46,030 --> 00:00:48,400
So let's write the function over here.

17
00:00:49,340 --> 00:00:52,910
Now we can call this function add two numbers.

18
00:00:57,080 --> 00:01:01,130
Now this function is going to take in the head of the two linked lists.

19
00:01:01,160 --> 00:01:01,520
All right.

20
00:01:01,520 --> 00:01:04,430
So let's just call the head L1 and L2.

21
00:01:06,790 --> 00:01:12,220
Now, once inside the function, first let's have a variable called called carry forward.

22
00:01:12,220 --> 00:01:13,960
So let's say carry forward.

23
00:01:15,130 --> 00:01:18,370
Is initially initialized to zero, so it's equal to zero.

24
00:01:18,370 --> 00:01:19,960
And then we will calculate it later.

25
00:01:19,960 --> 00:01:22,060
So let's carry forward equal to zero.

26
00:01:22,060 --> 00:01:24,370
Now we will have a new linked list.

27
00:01:24,370 --> 00:01:25,750
So let's say const.

28
00:01:26,960 --> 00:01:32,000
And let's call it results is equal to new linked list.

29
00:01:33,400 --> 00:01:37,990
So we are using the linked list class to initialize a results object over here.

30
00:01:38,020 --> 00:01:39,640
Now we are going to have a while loop.

31
00:01:39,640 --> 00:01:46,060
And as we discussed in the video where we discussed the method, we have to keep iterating as long as

32
00:01:46,300 --> 00:01:51,730
there is something in either of the linked list which is given to us, or if the carry forward is not

33
00:01:51,730 --> 00:01:52,120
zero.

34
00:01:52,120 --> 00:01:56,590
So over here we are going to have while l one is true or.

35
00:01:57,710 --> 00:01:59,060
L2 is true.

36
00:01:59,940 --> 00:02:01,860
Or carry forward is true.

37
00:02:01,860 --> 00:02:02,220
All right.

38
00:02:02,220 --> 00:02:08,730
So even if L1 and L2 is pointing to null and there is some carry forward, even then we have to iterate.

39
00:02:08,730 --> 00:02:10,650
So this is the condition for the while loop.

40
00:02:10,650 --> 00:02:15,480
Now inside this we are going to calculate the value of L1 and L2.

41
00:02:15,480 --> 00:02:18,600
That is the value in the node L1 and L2.

42
00:02:18,600 --> 00:02:21,870
So for this let's say let L1 value.

43
00:02:24,610 --> 00:02:25,480
Is equal to.

44
00:02:25,480 --> 00:02:31,840
And then we have a condition if L1 is truthy, if there is a node over there then we'll just take L1

45
00:02:31,840 --> 00:02:32,770
dot value.

46
00:02:33,640 --> 00:02:36,460
Otherwise we will just take it as zero.

47
00:02:36,880 --> 00:02:40,270
Similarly for L2 also let's have a variable L2 value.

48
00:02:41,710 --> 00:02:46,150
Now, if L2 is truthy then we will take the value of L2.

49
00:02:46,150 --> 00:02:47,620
So l2 dot value.

50
00:02:47,980 --> 00:02:49,960
Otherwise we will take it as zero.

51
00:02:50,020 --> 00:02:50,500
All right.

52
00:02:50,500 --> 00:02:55,570
So this is important because we have seen that the linked list can be of different length.

53
00:02:55,570 --> 00:02:59,080
And even there can be a case where L1 and L2 are false.

54
00:02:59,080 --> 00:03:00,940
But there is something in carry forward.

55
00:03:00,940 --> 00:03:01,330
All right.

56
00:03:01,330 --> 00:03:03,550
So we have seen that in the explainer video.

57
00:03:03,550 --> 00:03:08,740
Now let's add these values so we can again have one more variable let's say sum.

58
00:03:09,340 --> 00:03:11,410
And this is going to be equal to.

59
00:03:12,630 --> 00:03:13,680
L1 value.

60
00:03:14,870 --> 00:03:16,160
Plus L2 value.

61
00:03:17,620 --> 00:03:19,030
Plus carry forward.

62
00:03:21,760 --> 00:03:22,390
All right.

63
00:03:22,390 --> 00:03:24,220
And this is this is the sum.

64
00:03:24,220 --> 00:03:27,850
And then we want to know what value we should have in the node.

65
00:03:27,850 --> 00:03:28,030
Right.

66
00:03:28,030 --> 00:03:30,160
So let's say let's have a variable for that.

67
00:03:30,160 --> 00:03:31,990
So we could do it here itself.

68
00:03:31,990 --> 00:03:33,940
But let's just make it more readable.

69
00:03:33,940 --> 00:03:35,380
So let's say let.

70
00:03:37,380 --> 00:03:38,130
Node.

71
00:03:38,930 --> 00:03:40,010
Value.

72
00:03:41,220 --> 00:03:42,300
In result.

73
00:03:43,220 --> 00:03:46,400
Be equal to some percentage ten.

74
00:03:46,400 --> 00:03:49,220
So we are dividing it by ten and taking the remainder.

75
00:03:49,220 --> 00:03:52,610
So this is going to be the value of the node in the results array.

76
00:03:52,820 --> 00:03:57,200
Now we just have to add this at the tail to the results linked list.

77
00:03:57,200 --> 00:04:00,020
So we can say results dot add a tail.

78
00:04:01,230 --> 00:04:05,340
And then we are going to pass in the value over here, which is node value in result.

79
00:04:08,390 --> 00:04:08,960
All right.

80
00:04:08,960 --> 00:04:10,430
So so that is it.

81
00:04:10,430 --> 00:04:13,310
So now we also need to check if there is a carry forward.

82
00:04:13,310 --> 00:04:17,420
So let's say carry forward is equal to math dot floor.

83
00:04:18,800 --> 00:04:20,360
And we are taking the sum.

84
00:04:20,360 --> 00:04:20,870
All right.

85
00:04:20,870 --> 00:04:23,450
So we are taking the sum which is uh sum.

86
00:04:23,870 --> 00:04:25,820
And then we divide this by ten.

87
00:04:25,820 --> 00:04:28,760
So this will give us if there is any carry forward.

88
00:04:28,760 --> 00:04:29,390
All right.

89
00:04:30,160 --> 00:04:35,140
And once we are done with this, we just have to move forward in the two linked lists.

90
00:04:35,140 --> 00:04:40,690
So again, you we cannot simply say L1 dot next because we don't know whether it's null.

91
00:04:40,690 --> 00:04:40,900
Right.

92
00:04:40,900 --> 00:04:47,230
Because over here the condition is if L1 is L1 or L2 or carry forward is truthy, we come inside.

93
00:04:47,230 --> 00:04:50,560
So again we have to check if L1 is truthy.

94
00:04:50,560 --> 00:04:52,750
So we can say L1 is equal to.

95
00:04:52,750 --> 00:04:57,220
And if L1 is truthy then we will say L1 dot next.

96
00:04:59,490 --> 00:05:01,800
Otherwise we will just say null.

97
00:05:02,850 --> 00:05:03,270
All right.

98
00:05:03,270 --> 00:05:06,990
Similarly for L2 also L2 is equal to.

99
00:05:07,890 --> 00:05:12,300
If L2 is truthy, then we will say L2 dot next.

100
00:05:13,380 --> 00:05:14,460
Otherwise null.

101
00:05:16,900 --> 00:05:17,680
And that's it.

102
00:05:17,680 --> 00:05:22,840
So once we're out of this while loop, we will have our results linked list.

103
00:05:22,840 --> 00:05:28,270
And then we just need to return this linked list so we can say return results.

104
00:05:29,260 --> 00:05:29,980
And that is it.

105
00:05:29,980 --> 00:05:30,550
This should work.

106
00:05:30,550 --> 00:05:32,800
So let's go ahead and test our code.

107
00:05:32,800 --> 00:05:35,650
So again we have set up the test case over here.

108
00:05:35,650 --> 00:05:38,950
So we are going to add 745 40 and 723.

109
00:05:38,950 --> 00:05:40,390
So let's use our function.

110
00:05:40,390 --> 00:05:42,190
So we have add two numbers.

111
00:05:42,190 --> 00:05:46,180
And we are going to pass in the head of linked list n1 and n2.

112
00:05:46,210 --> 00:05:51,430
So over here we will pass n1 dot head and n2 dot head.

113
00:05:54,280 --> 00:05:54,730
All right.

114
00:05:54,760 --> 00:05:58,000
Now let's go ahead and call the function and see what we are getting.

115
00:05:59,940 --> 00:06:05,250
So you can see we have the results, which is a linked list with four nodes.

116
00:06:05,250 --> 00:06:06,150
That is correct.

117
00:06:06,180 --> 00:06:09,180
1002 63 has four digits over here.

118
00:06:09,210 --> 00:06:10,440
Now let's open it up.

119
00:06:10,440 --> 00:06:11,790
And again it's reverse right.

120
00:06:11,790 --> 00:06:13,080
So first it should be three.

121
00:06:13,080 --> 00:06:14,940
So yes we have three at the head.

122
00:06:14,940 --> 00:06:17,340
And then three is pointing to six which is correct.

123
00:06:17,340 --> 00:06:18,660
Which is what we have over here.

124
00:06:18,660 --> 00:06:20,670
And six is pointing to two.

125
00:06:20,700 --> 00:06:21,720
That is also correct.

126
00:06:21,720 --> 00:06:22,770
So we have two over here.

127
00:06:22,770 --> 00:06:25,350
And then two is pointing to one which is correct.

128
00:06:25,350 --> 00:06:27,870
So we have one over here and that is pointing to null.

129
00:06:27,870 --> 00:06:29,520
So yes our code is working.

130
00:06:29,610 --> 00:06:30,030
All right.

131
00:06:30,030 --> 00:06:33,120
Now let's just walk through the code with this example over here.

132
00:06:33,780 --> 00:06:36,030
So let me just take a pen for this.

133
00:06:36,570 --> 00:06:41,910
So we have 540 plus 723, and the linked lists are stored in reverse order.

134
00:06:41,910 --> 00:06:45,360
So we have zero pointing to four pointing to five.

135
00:06:45,570 --> 00:06:49,860
And then we have three pointing to two pointing to seven.

136
00:06:49,860 --> 00:06:51,300
So these are the heads of these.

137
00:06:51,300 --> 00:06:51,750
All right.

138
00:06:51,750 --> 00:06:53,940
So let's go ahead and see what's happening over here.

139
00:06:53,940 --> 00:06:57,120
Now we call the add two numbers function.

140
00:06:57,120 --> 00:06:58,590
Now let's go to that part.

141
00:06:58,590 --> 00:07:00,270
So we are inside the function over here.

142
00:07:00,270 --> 00:07:03,720
And we have the heads which is zero and three which is L1 and L2.

143
00:07:03,720 --> 00:07:06,120
Now carry forward is initialized to zero.

144
00:07:06,150 --> 00:07:09,720
And then we make a new linked list which is results.

145
00:07:09,720 --> 00:07:11,940
At this point results is just null.

146
00:07:11,970 --> 00:07:17,280
Now we see that if L1 or L2 or carry forward is truthy, we have to iterate.

147
00:07:17,280 --> 00:07:20,520
And we see that initially L1 is this head right.

148
00:07:20,520 --> 00:07:23,220
This is L1 and this is L2 and both are truthy.

149
00:07:23,220 --> 00:07:24,780
So we come inside the while loop.

150
00:07:24,780 --> 00:07:28,740
Now we we identify L1 value as the value of L1.

151
00:07:28,740 --> 00:07:31,080
Because L1 is truthy that's equal to zero.

152
00:07:31,080 --> 00:07:33,540
And then L2 value is going to be equal to three.

153
00:07:34,240 --> 00:07:39,340
And some is going to be zero plus three plus carry forward and carry forward is equal to zero.

154
00:07:39,340 --> 00:07:41,710
So some now is going to be equal to three.

155
00:07:42,070 --> 00:07:45,250
And then we are going to do three percentage ten right.

156
00:07:45,250 --> 00:07:46,810
So that gives us three itself.

157
00:07:46,810 --> 00:07:49,420
So the node value in the result is going to be three.

158
00:07:49,420 --> 00:07:56,200
And then we are going to create a node and add it at the tail of the results linked list.

159
00:07:56,200 --> 00:07:59,080
So the results linked list is just null over here at this point.

160
00:07:59,080 --> 00:08:01,510
So we're just making a node over here with three.

161
00:08:01,510 --> 00:08:03,040
And this is pointing to null.

162
00:08:03,040 --> 00:08:06,850
And then we are going to calculate carry forward which is math dot floor.

163
00:08:06,850 --> 00:08:09,250
Some is three three by ten is 0.3.

164
00:08:09,250 --> 00:08:11,440
And when we floor it we will get zero itself.

165
00:08:11,440 --> 00:08:13,600
So carry forward is again zero over here.

166
00:08:14,980 --> 00:08:15,430
All right.

167
00:08:15,460 --> 00:08:16,450
Now let's proceed.

168
00:08:16,450 --> 00:08:17,920
And then L1 is moving.

169
00:08:17,920 --> 00:08:21,580
L1 is equal to L1 dot next and L2 is equal to L2 dot next over here.

170
00:08:21,580 --> 00:08:24,310
So L1 comes over here and L2 comes over here.

171
00:08:24,310 --> 00:08:26,410
And then again we come over here and we check.

172
00:08:26,410 --> 00:08:28,000
So we see both of them are truthy.

173
00:08:28,000 --> 00:08:31,780
So we come inside and we find their value as four and two.

174
00:08:31,780 --> 00:08:34,690
And then sum is equal to four plus two which is equal to six.

175
00:08:34,690 --> 00:08:39,490
Now node value in results this is going to be six percentage ten which is six itself.

176
00:08:39,490 --> 00:08:43,000
And then we are going to create a node with value six.

177
00:08:43,000 --> 00:08:44,920
And we are adding it at the tail.

178
00:08:44,920 --> 00:08:46,450
So the tail over here is here right.

179
00:08:46,450 --> 00:08:47,740
So we're going to add it over here.

180
00:08:47,740 --> 00:08:49,120
So we have six over here.

181
00:08:49,120 --> 00:08:51,160
And this is pointed in this direction.

182
00:08:51,160 --> 00:08:56,980
So for this we are using the add a tail function which we have written in the video where we constructed

183
00:08:56,980 --> 00:08:58,630
the linked list singly linked list.

184
00:08:58,630 --> 00:08:59,170
All right.

185
00:08:59,170 --> 00:09:00,340
So this is done again.

186
00:09:00,340 --> 00:09:02,410
We come over here we calculate the carry forward.

187
00:09:02,410 --> 00:09:03,880
So that's going to be six by ten.

188
00:09:03,880 --> 00:09:06,490
And then flooring it which is again equal to zero.

189
00:09:06,490 --> 00:09:08,440
So the carry forward is still equal to zero.

190
00:09:08,470 --> 00:09:11,290
Now L1 and L2 are moved forward.

191
00:09:11,290 --> 00:09:15,580
So we get L1 is equal to L1 dot next which is over here.

192
00:09:15,580 --> 00:09:18,820
And L2 is equal to L2 dot next which is over here.

193
00:09:18,820 --> 00:09:19,330
All right.

194
00:09:19,330 --> 00:09:20,230
Again we come over here.

195
00:09:20,230 --> 00:09:21,310
We see they are truthy.

196
00:09:21,310 --> 00:09:24,340
So we are going to take their values which is five and seven.

197
00:09:24,340 --> 00:09:26,740
And then we add it up and carry forward is zero.

198
00:09:26,740 --> 00:09:28,600
So five plus seven plus zero.

199
00:09:28,600 --> 00:09:30,100
That's equal to 12.

200
00:09:30,700 --> 00:09:32,440
So sum is equal to 12.

201
00:09:32,470 --> 00:09:37,450
Now note value is equal to 12 percentage ten which is equal to two right.

202
00:09:37,450 --> 00:09:38,560
So that's equal to two.

203
00:09:38,590 --> 00:09:43,510
So over here we are going to add at the tail a node with value two.

204
00:09:43,540 --> 00:09:44,650
So the tail is over here.

205
00:09:44,650 --> 00:09:46,360
So we have a node with value two.

206
00:09:46,360 --> 00:09:47,620
And this is going to point over here.

207
00:09:47,620 --> 00:09:48,820
And this is the new tail.

208
00:09:48,910 --> 00:09:53,500
Now carry forward is calculated as 12 which is the sum divided by ten.

209
00:09:53,500 --> 00:09:55,390
That's equal to 1.2.

210
00:09:55,390 --> 00:09:58,000
And then when we flow it we will get that as one.

211
00:09:58,000 --> 00:10:00,730
So one carry forward now is equal to one.

212
00:10:02,270 --> 00:10:02,990
All right.

213
00:10:03,680 --> 00:10:07,190
Again, we check if L1 is truthy.

214
00:10:07,190 --> 00:10:07,970
Yes, it's truthy.

215
00:10:07,970 --> 00:10:10,700
So we are going to do L1 dot next.

216
00:10:10,700 --> 00:10:12,860
And this is anyway pointing to null right.

217
00:10:12,860 --> 00:10:15,170
So over here this is pointing to null.

218
00:10:16,100 --> 00:10:17,930
And this is also pointing to null.

219
00:10:17,930 --> 00:10:18,800
So L1 dot.

220
00:10:18,800 --> 00:10:21,620
Next when we do L1 dot next we get over here.

221
00:10:21,620 --> 00:10:25,070
Similarly L2 dot next is also going to get us over here.

222
00:10:25,070 --> 00:10:29,210
Now when we come to the while loop condition we see that L1 is null.

223
00:10:29,210 --> 00:10:32,210
L2 is also null, but carry forward is equal to one.

224
00:10:32,210 --> 00:10:35,720
So that's why we again come inside over here inside the while loop.

225
00:10:35,720 --> 00:10:40,430
And over here we see that L1 is falsy because it's null right.

226
00:10:40,430 --> 00:10:42,830
So we're going to take L1 value as zero.

227
00:10:43,490 --> 00:10:45,680
And L2 also is falsy.

228
00:10:45,680 --> 00:10:47,690
So L2 value is going to be equal to zero.

229
00:10:47,720 --> 00:10:49,040
That's what we're doing over here.

230
00:10:49,040 --> 00:10:53,870
And then sum is equal to zero plus zero plus one because carry forward is equal to one.

231
00:10:53,870 --> 00:10:55,910
So we're getting the sum as equal to one.

232
00:10:55,910 --> 00:10:58,910
And then node value is equal to one percentage ten.

233
00:10:58,910 --> 00:11:01,010
And that's equal to one itself.

234
00:11:01,010 --> 00:11:01,190
Right.

235
00:11:01,190 --> 00:11:03,140
So we're going to make a node with value one.

236
00:11:03,140 --> 00:11:06,710
And using this line of code we are inserting it at the tail.

237
00:11:06,710 --> 00:11:09,080
So we are having a new node with value one.

238
00:11:09,080 --> 00:11:10,520
And this is inserted over here.

239
00:11:10,520 --> 00:11:12,800
And two is pointing to one at this moment.

240
00:11:12,800 --> 00:11:17,210
And then we again calculate carry forward which is one divided by ten.

241
00:11:17,210 --> 00:11:19,100
And we are flowing it which is equal to zero.

242
00:11:19,100 --> 00:11:25,490
So now carry forward becomes zero and then L1 is falsy so L1 is just null and L2 is just null.

243
00:11:25,490 --> 00:11:27,260
And then carry forward is also zero.

244
00:11:27,260 --> 00:11:32,690
Again when we come over here we see L1 is null, L2 is null, and carry forward is zero.

245
00:11:32,690 --> 00:11:38,090
So this becomes falsy and we come out of it and we are just going to return the linked list over here,

246
00:11:38,090 --> 00:11:41,330
which is three pointing to six pointing to two pointing to one.

247
00:11:41,330 --> 00:11:42,470
And that is the output.

248
00:11:42,470 --> 00:11:44,330
So this is how this function works.

249
00:11:44,720 --> 00:11:48,290
Now what about the space and time complexity of this solution.

250
00:11:48,290 --> 00:11:52,970
The time complexity is going let's say we have two linked lists of length m and n.

251
00:11:53,920 --> 00:11:56,980
Now we have to traverse the whole linked list.

252
00:11:56,980 --> 00:11:57,310
Right.

253
00:11:57,310 --> 00:12:02,410
So whichever is greater, that would determine the number of operations we need to traverse the linked

254
00:12:02,410 --> 00:12:02,680
list.

255
00:12:02,680 --> 00:12:07,870
So that's why the time complexity is going to be O of maximum among m and n.

256
00:12:09,020 --> 00:12:14,450
And the space complexity is also equal to the same thing, because we are going to have an output array

257
00:12:14,720 --> 00:12:21,140
output linked list, and the size of the output linked list can be maximum max of m comma n plus one.

258
00:12:21,140 --> 00:12:21,410
Right.

259
00:12:21,410 --> 00:12:25,910
So over here you can see we have an extra node over here compared to the length of the linked list because

260
00:12:25,910 --> 00:12:27,290
there was something in the carry forward.

261
00:12:27,290 --> 00:12:33,470
So that's why we can say the maximum length of the linked list is going to be maximum between M and

262
00:12:33,470 --> 00:12:34,250
N plus one.

263
00:12:34,250 --> 00:12:40,610
So that's why we can say the space complexity of this solution is also of the order of max of m and

264
00:12:40,610 --> 00:12:46,430
n, where m and n are the respective sizes or lengths of the linked list which is given to us.