1
00:00:02,020 --> 00:00:02,740
Hi, everyone.

2
00:00:02,770 --> 00:00:07,060
So today we are going to solve this question intersection of two linked list.

3
00:00:07,530 --> 00:00:10,210
OK, so we are provided with the Dooling list.

4
00:00:10,240 --> 00:00:17,410
So this is our first linked list, linked list and this is our second link list linked list B, OK,

5
00:00:17,590 --> 00:00:21,590
so we have to find the intersection point and the intersection point is seven.

6
00:00:21,700 --> 00:00:23,680
OK, so this should be our output.

7
00:00:25,030 --> 00:00:31,280
OK, so this is the first linked list starting from even and it ends at Citrix and this is our second

8
00:00:31,280 --> 00:00:35,110
link list starting from BE1 and it will end it Sheetrit.

9
00:00:35,380 --> 00:00:39,430
OK, and basically our intersection, we have to find the intersection.

10
00:00:39,820 --> 00:00:41,650
So the intersection is seven.

11
00:00:41,710 --> 00:00:43,690
OK, so this should be our output.

12
00:00:43,720 --> 00:00:45,580
OK, we have to output this node.

13
00:00:46,090 --> 00:00:48,540
So this question is present only record.

14
00:00:49,050 --> 00:00:51,460
OK, so intersection of the two linked list.

15
00:00:52,120 --> 00:00:55,810
So as you can see here, so this is the first example.

16
00:00:55,960 --> 00:01:02,230
So linked list here for one eight four five and linked list B five zero one eight four five.

17
00:01:02,530 --> 00:01:04,180
So our output should be eight.

18
00:01:04,220 --> 00:01:11,140
OK, now let's see one more examples of included, which is zero nine one two four and linked list B,

19
00:01:11,140 --> 00:01:13,720
which is three to four for output.

20
00:01:13,720 --> 00:01:14,470
Should be two.

21
00:01:15,560 --> 00:01:21,440
Now, here, this is a special case in this case, the English do not intersect, so the list is two

22
00:01:21,440 --> 00:01:23,810
six four and the English is one in five.

23
00:01:24,020 --> 00:01:27,010
OK, so in this case, our output should be nil.

24
00:01:27,770 --> 00:01:30,710
OK, and these are some of the notes.

25
00:01:30,740 --> 00:01:32,060
OK, so what we have to do.

26
00:01:34,630 --> 00:01:40,060
So first of all, if the ruling list do not intersect, OK, if there is no intersection point, then

27
00:01:40,060 --> 00:01:46,230
our output should be OK and we do not have to change the linked list, OK?

28
00:01:46,270 --> 00:01:47,610
We do not change the linked list.

29
00:01:47,620 --> 00:01:51,130
We will not change the structure of linked list must remain the same.

30
00:01:51,400 --> 00:01:53,530
And we can assume there are no cycles.

31
00:01:53,560 --> 00:01:55,350
OK, no cycle.

32
00:01:55,720 --> 00:02:03,580
For example, this is the first linked list even if you a tree and suppose there is a cycle if one is

33
00:02:03,580 --> 00:02:04,810
pointing towards a tree.

34
00:02:04,840 --> 00:02:08,500
OK, so this is a cycle now in this problem cycle will not be there.

35
00:02:08,530 --> 00:02:16,260
OK, we can assume there are no cycles and preferably I would call children at one time and one space.

36
00:02:16,300 --> 00:02:19,630
OK, so we have to take linear time and constant space.

37
00:02:20,440 --> 00:02:22,740
OK, now let us try to solve this problem.

38
00:02:22,750 --> 00:02:24,850
So how we will approach this problem.

39
00:02:25,180 --> 00:02:29,920
OK, so first of all, let us think about the brute force approach and very naive approach that we used

40
00:02:29,920 --> 00:02:31,810
to that we used in Eddie.

41
00:02:32,190 --> 00:02:36,000
OK, so what we can do here is so first what we will do.

42
00:02:36,010 --> 00:02:39,210
So let us discuss approach number one.

43
00:02:39,940 --> 00:02:41,770
OK, so brute force approach.

44
00:02:44,210 --> 00:02:46,490
So the first so the first approach is.

45
00:02:47,710 --> 00:02:51,730
Pick the first node and then I tripped over the second link list.

46
00:02:53,000 --> 00:02:59,200
OK, they will not be any match, then pick the second or the first link list and again, I tripped

47
00:02:59,220 --> 00:03:03,200
over the second link list again, there will be no match.

48
00:03:03,620 --> 00:03:08,970
Then pick the third node and then again I did over that second link list.

49
00:03:08,990 --> 00:03:11,060
Now, in this case, there will be a match.

50
00:03:11,450 --> 00:03:14,520
OK, so if there is a match, we can output our result.

51
00:03:15,290 --> 00:03:20,870
OK, and similarly, at this point, our program will stop and we will return soon.

52
00:03:21,320 --> 00:03:23,400
OK, so this is what we will do.

53
00:03:23,420 --> 00:03:26,840
So suppose we have to areas Eddie and Araby.

54
00:03:26,840 --> 00:03:35,980
So Eddie has some elements, even E2 and E3 and Araby we when we do be three and before.

55
00:03:36,200 --> 00:03:41,600
So the approach is very simple because the first element I did with the secondary pick, the second

56
00:03:41,600 --> 00:03:43,700
element again, I did all the secondary.

57
00:03:44,300 --> 00:03:49,940
The third element I did over the secondary picked the fourth element for telemedicine out there at eight

58
00:03:49,970 --> 00:03:53,030
finished and we did not find any intersection point.

59
00:03:53,210 --> 00:03:55,810
So that means at the and we do not intersect.

60
00:03:55,820 --> 00:03:57,470
So in this case we can return.

61
00:03:57,770 --> 00:03:59,930
OK, so this is the brute force approach.

62
00:04:00,920 --> 00:04:03,090
So what will be the time and the space complexity?

63
00:04:03,470 --> 00:04:08,000
So in the case of brute force, approach the time, complexities what we are doing here.

64
00:04:08,000 --> 00:04:09,470
Let's do the list.

65
00:04:09,470 --> 00:04:14,600
Let's say the length of the first Linklaters M and the length of the second link list is N, so the

66
00:04:14,610 --> 00:04:21,800
time, complexities and doing OK and the space complexities of an OK constraint space.

67
00:04:22,070 --> 00:04:23,870
Now let us try to call this OK.

68
00:04:27,070 --> 00:04:29,170
So I will be writing C++.

69
00:04:31,590 --> 00:04:37,380
So we are provided with the two link list, link list and linked list be OK and we have to return the

70
00:04:37,380 --> 00:04:38,280
intersection point.

71
00:04:38,670 --> 00:04:40,630
OK, so what is our approach?

72
00:04:41,250 --> 00:04:42,180
So let's say.

73
00:04:44,380 --> 00:04:45,660
It is not close to Nel.

74
00:04:46,960 --> 00:04:53,410
Armatrading over the first link list, and now what I will do, I will select the first node, I will

75
00:04:53,410 --> 00:04:58,500
select every note of linked list and then I will take over the list, be OK.

76
00:04:58,810 --> 00:05:01,570
So since we have to ideato the second link list.

77
00:05:02,650 --> 00:05:09,970
So I'm digging appointer now at this point that it will point it will point towards the head of.

78
00:05:10,930 --> 00:05:13,270
So this is head.

79
00:05:14,370 --> 00:05:19,350
Had to and this is pointing towards me, OK, now we have to did.

80
00:05:20,530 --> 00:05:26,740
Over this link list, so while hairdo is not a questionable.

81
00:05:31,170 --> 00:05:32,520
Now we just have to check.

82
00:05:32,550 --> 00:05:36,300
OK, so we will check if a equals equals.

83
00:05:37,420 --> 00:05:38,020
Head to.

84
00:05:39,990 --> 00:05:42,870
Then we can return, there is an intersection point so we can return.

85
00:05:43,560 --> 00:05:47,490
OK, otherwise what we have to do so.

86
00:05:49,490 --> 00:05:50,990
Head to equals.

87
00:05:52,270 --> 00:05:53,410
Head to head on next.

88
00:05:54,880 --> 00:05:56,740
OK, and outside the wire loop.

89
00:05:58,290 --> 00:06:00,030
Equals next toffy.

90
00:06:02,220 --> 00:06:06,810
OK, now if the veil opens so we can safely say here.

91
00:06:09,800 --> 00:06:15,050
So if the veil opened, then we can say there is no intersection point, OK, so we will have tunnel.

92
00:06:16,730 --> 00:06:20,600
OK, so this is our very simple cold now let's try to end our good.

93
00:06:23,500 --> 00:06:25,030
OK, so this will be had to.

94
00:06:30,040 --> 00:06:32,140
OK, so our guard got accepted.

95
00:06:33,580 --> 00:06:34,870
Now at let's try to it.

96
00:06:38,000 --> 00:06:42,530
OK, so our goal is getting accepted, but it is not very good.

97
00:06:42,860 --> 00:06:45,160
OK, so we can do optimisations.

98
00:06:46,100 --> 00:06:51,290
So what optimization that we can do here is so first of all, the time complexity of this code.

99
00:06:53,250 --> 00:06:55,410
So we discussed the first approach.

100
00:06:56,500 --> 00:07:04,000
Which is the brute force approach, time, complexity is Emman and the space complexities own.

101
00:07:04,150 --> 00:07:06,650
OK, let's discuss the second approach.

102
00:07:07,000 --> 00:07:09,580
So the second approach will make use of map.

103
00:07:09,930 --> 00:07:13,870
OK, so what we are going to do is so let us take an example.

104
00:07:18,080 --> 00:07:19,550
So let us take one example.

105
00:07:20,450 --> 00:07:30,590
So for one eight four five, so for one eight, four, five and we have second long list.

106
00:07:31,520 --> 00:07:32,330
Five 01.

107
00:07:34,660 --> 00:07:37,660
So this is five zero and one.

108
00:07:38,840 --> 00:07:42,800
OK, so our output should be right now with the help of MAP.

109
00:07:43,820 --> 00:07:45,060
How can we solve this problem?

110
00:07:45,380 --> 00:07:52,040
So what we are going to do here is so this is our first linked list and this is our second linked list.

111
00:07:52,310 --> 00:07:54,400
So pick any linked list.

112
00:07:54,410 --> 00:07:57,590
For example, I am picking, let's say, second linked list.

113
00:07:57,590 --> 00:08:04,310
You can pick it also, but let's say I am picking B, OK, now what we will do, we will take a map

114
00:08:04,790 --> 00:08:11,270
and the structure of the map will be so the key will be node and the value will be, let's say a boolean

115
00:08:11,270 --> 00:08:11,510
value.

116
00:08:11,510 --> 00:08:12,230
True or false.

117
00:08:12,260 --> 00:08:14,580
OK, so boolean value, true or false.

118
00:08:14,840 --> 00:08:22,010
Now we will iterate over link list B, ok, suppose I am choosing wrinklies B so will I do it over the

119
00:08:22,010 --> 00:08:22,810
second link list.

120
00:08:23,060 --> 00:08:23,570
So what.

121
00:08:23,570 --> 00:08:25,670
It will do so five.

122
00:08:26,600 --> 00:08:32,179
First, five six five zero zero Drew when Drew.

123
00:08:33,090 --> 00:08:37,400
Eight through, four through and five through.

124
00:08:38,110 --> 00:08:41,070
OK, so this will be the structure of our map.

125
00:08:41,330 --> 00:08:43,429
OK, so this will be our map.

126
00:08:44,220 --> 00:08:50,800
So once our map is ready, what we will do, we will trade over the second link list, the remaining

127
00:08:50,800 --> 00:08:52,290
link list, which we didn't choose.

128
00:08:52,330 --> 00:08:55,790
OK, so I choose B for making the map.

129
00:08:56,100 --> 00:08:58,170
Now I will iterate over the linked list.

130
00:08:58,620 --> 00:09:01,470
OK, so Fort so is four percent.

131
00:09:01,680 --> 00:09:02,830
So these are not values.

132
00:09:02,850 --> 00:09:06,630
OK, so this is value but I am storing node.

133
00:09:06,830 --> 00:09:11,940
OK, so basically I am storing five and I am also storing the address of its next node.

134
00:09:11,970 --> 00:09:13,810
OK, I am not storing the value.

135
00:09:14,160 --> 00:09:17,040
So this four and this four, they are not equal.

136
00:09:17,140 --> 00:09:19,960
OK, I am storing the node I list or node.

137
00:09:20,010 --> 00:09:23,370
OK, so this four and this four they are not a.

138
00:09:23,940 --> 00:09:25,300
Please do not get confused.

139
00:09:25,830 --> 00:09:29,790
So the structure of node is so it will store the value.

140
00:09:30,180 --> 00:09:33,570
And I have a pointer next and this is the address.

141
00:09:34,470 --> 00:09:37,650
OK, so when I am comparing the node we are storing node.

142
00:09:37,950 --> 00:09:43,390
So when we are comparing the node we are comparing the value and we are also comparing the next pointer.

143
00:09:43,630 --> 00:09:46,680
OK, so here I am storing two things.

144
00:09:46,680 --> 00:09:48,720
Five and the next pointer.

145
00:09:49,590 --> 00:09:52,510
So this four and this war, they are not equal.

146
00:09:52,570 --> 00:09:56,450
OK, then I will compare, then I will compare one.

147
00:09:56,610 --> 00:09:57,800
So is one present.

148
00:09:57,810 --> 00:10:01,140
Yes, one is not present, one is present but they are not equal.

149
00:10:01,140 --> 00:10:02,390
OK, not equal.

150
00:10:02,400 --> 00:10:03,110
Why not equal.

151
00:10:03,120 --> 00:10:04,520
Because the next pointer is different.

152
00:10:05,160 --> 00:10:07,500
It now eight percent.

153
00:10:07,510 --> 00:10:08,760
Yes it is present.

154
00:10:09,030 --> 00:10:10,430
So here what will happen.

155
00:10:11,010 --> 00:10:15,450
Value will we get matched and the next pointer will also get matched.

156
00:10:15,480 --> 00:10:17,300
OK, because we are storing the node.

157
00:10:17,640 --> 00:10:21,600
So since both the values get matched so we can return.

158
00:10:21,660 --> 00:10:23,340
OK, so here we will return eight.

159
00:10:24,810 --> 00:10:25,530
Return eight.

160
00:10:25,680 --> 00:10:28,640
OK, so this is how we can use map.

161
00:10:28,950 --> 00:10:30,560
Now what will the time complexity.

162
00:10:30,930 --> 00:10:32,800
So the time complexity will be.

163
00:10:32,820 --> 00:10:37,710
So first of all I am making this map OK, so we will use an algorithm.

164
00:10:37,950 --> 00:10:42,640
Basically we can assume the access time is constraint, OK, or when existing.

165
00:10:43,200 --> 00:10:49,830
So first of all I maltreating all the list B and let's say it's lent to them and it's Lento's.

166
00:10:49,830 --> 00:10:55,380
And so first of all, am I taking over the linked list B to make the map.

167
00:10:55,380 --> 00:10:59,820
So N then I will trade over the first link list.

168
00:11:01,050 --> 00:11:06,300
And so the time complexities basically in place and all you can see, linear time, complexity, OK,

169
00:11:06,300 --> 00:11:06,750
linear.

170
00:11:07,950 --> 00:11:13,920
And what is this to respond collectively to, let's say, if I am choosing B, so those complexities

171
00:11:13,920 --> 00:11:19,060
are often OK, so I am assuming here that this time of using the map is open.

172
00:11:19,600 --> 00:11:21,840
OK, we are using an order to map.

173
00:11:22,770 --> 00:11:22,930
Case.

174
00:11:22,960 --> 00:11:24,870
So basically there are two types of maps.

175
00:11:26,250 --> 00:11:28,140
First one is the unordered MEB.

176
00:11:29,060 --> 00:11:30,380
And the second one is.

177
00:11:31,340 --> 00:11:31,820
Map.

178
00:11:32,300 --> 00:11:41,330
OK, so an order means basically we will use a hash table to implement the road map and for implementing

179
00:11:41,330 --> 00:11:44,130
the map, basically we use a balanced body.

180
00:11:45,170 --> 00:11:45,580
OK.

181
00:11:47,450 --> 00:11:51,260
Basically, right BlackBerry now let us implement this approach.

182
00:11:54,230 --> 00:11:58,870
So I will come into the school and I will write the code again.

183
00:12:08,160 --> 00:12:11,640
OK, so first of all, we have to make an order to map.

184
00:12:14,610 --> 00:12:19,140
Now, the road map, the key value will be the node.

185
00:12:20,680 --> 00:12:22,500
And the value is bull.

186
00:12:23,290 --> 00:12:25,950
OK, so let's say the name is my Miep.

187
00:12:27,970 --> 00:12:33,940
Now, what we have to do, we have to pick and include, let's say I am picking B so to make our map

188
00:12:33,940 --> 00:12:34,240
ready.

189
00:12:34,270 --> 00:12:41,080
So while B is not well, I am maltreating or the second link list and what we have to do.

190
00:12:41,560 --> 00:12:45,790
So my map of B is true.

191
00:12:47,550 --> 00:12:51,960
OK, and then B equals next B.

192
00:13:00,340 --> 00:13:06,760
OK, so at this point, our map is ready now what we have to do, we have to iterate over the first

193
00:13:06,760 --> 00:13:07,320
link list.

194
00:13:07,330 --> 00:13:10,060
So vile is not a personal.

195
00:13:13,290 --> 00:13:18,540
And now we will check whether the node of the first linked list is present in the map or not.

196
00:13:18,570 --> 00:13:20,220
OK, so if.

197
00:13:21,920 --> 00:13:25,360
My map that count and I will give it.

198
00:13:25,520 --> 00:13:28,140
So this can't function what it will do.

199
00:13:28,160 --> 00:13:32,270
It will check whether the node is present in map or not.

200
00:13:32,780 --> 00:13:41,300
OK, so if it is present, if the node is present in map, if the node is present in this map, that

201
00:13:41,300 --> 00:13:44,910
means this node was also present in the second link list.

202
00:13:44,930 --> 00:13:47,010
That means this is the common node.

203
00:13:47,030 --> 00:13:49,020
OK, this is the other intersection.

204
00:13:49,430 --> 00:13:50,780
So we can simply return a.

205
00:13:52,050 --> 00:13:55,200
Otherwise, we will move ahead so equals.

206
00:13:57,680 --> 00:13:58,070
Next.

207
00:13:59,750 --> 00:14:05,090
OK, and if there's no intersection, we can simply a tunnel.

208
00:14:05,800 --> 00:14:09,620
OK, so at this point there is an intersection.

209
00:14:11,390 --> 00:14:16,880
OK, so what this current function will do, this current function will check whether this node is present

210
00:14:16,880 --> 00:14:18,230
inside the map or not.

211
00:14:18,260 --> 00:14:24,680
OK, so if this note is present inside the map, that that means this node was also present in the linked

212
00:14:24,680 --> 00:14:28,380
list B, OK, that's then only there can be an intersection.

213
00:14:28,790 --> 00:14:30,980
OK, so this is our complete code.

214
00:14:31,490 --> 00:14:34,820
Not just try to run out of code and then we will submit.

215
00:14:36,120 --> 00:14:36,570
OK.

216
00:14:40,410 --> 00:14:43,090
So our code is getting a separate OK?

217
00:14:43,110 --> 00:14:47,230
Our goal is right now we will discuss the best approach.

218
00:14:47,800 --> 00:14:48,210
OK.

219
00:14:50,500 --> 00:14:52,040
I'm commending the school.

220
00:14:52,720 --> 00:14:54,350
Now let us discuss the best approach.

221
00:14:54,370 --> 00:15:00,280
So we have discussed how to approach the brute force approach and the second one is my approach.

222
00:15:00,610 --> 00:15:03,490
OK, so this is the time complexity.

223
00:15:03,490 --> 00:15:05,010
So the time complexity is linear.

224
00:15:05,020 --> 00:15:07,120
We do not have any problem with the time, complexity.

225
00:15:07,460 --> 00:15:09,720
What we have problem is this space.

226
00:15:10,240 --> 00:15:14,410
What do you want to do here is we want this space to be constant over the space.

227
00:15:14,740 --> 00:15:18,640
OK, so this was the property of the problem, OK?

228
00:15:18,660 --> 00:15:22,660
So the problem, access to solve this problem in linear time, in space.

229
00:15:22,690 --> 00:15:28,870
So with the help of MAP, we can solve it in linear time, but it is taking on space and the space is

230
00:15:28,870 --> 00:15:29,670
due to map.

231
00:15:29,680 --> 00:15:32,670
We are we are creating map so that space is due to map.

232
00:15:32,860 --> 00:15:37,150
We want to optimize it to constrain space now how we can solve this problem.

233
00:15:37,720 --> 00:15:41,920
So what we are going to do here is so our approach will be very simple.

234
00:15:41,930 --> 00:15:43,480
So this is the first linked list.

235
00:15:44,440 --> 00:15:45,910
See when you do see three.

236
00:15:46,850 --> 00:15:53,600
And let's say this, our second link list, so B1, B2, B3.

237
00:15:55,200 --> 00:15:59,910
And before and then she went 23, OK, so what will you do?

238
00:16:01,120 --> 00:16:09,280
We will CDC's linked list and this is linked list, so we will use a very simple approach, OK, and

239
00:16:09,280 --> 00:16:12,700
approach will be first of all, we will find the length of linked list.

240
00:16:13,210 --> 00:16:18,830
So let's say this is AMSO and is basically an toffy offline, Kristie.

241
00:16:19,060 --> 00:16:22,150
So in this case, it will be one, two, three, four and five.

242
00:16:22,510 --> 00:16:23,660
So this will be five.

243
00:16:24,190 --> 00:16:28,630
Similarly, we will find the length of linked list.

244
00:16:28,870 --> 00:16:33,310
So in this case, it will be one, two, three, four, five, six and seven.

245
00:16:33,370 --> 00:16:35,560
OK, so this is seven.

246
00:16:36,340 --> 00:16:38,500
Then what we will do, we will subtract these two.

247
00:16:39,550 --> 00:16:41,060
OK, we will separate.

248
00:16:41,080 --> 00:16:43,150
So basically we will do and minus him.

249
00:16:43,870 --> 00:16:46,900
OK, so what will happen after this election?

250
00:16:47,320 --> 00:16:49,750
After this election, we will get to OK.

251
00:16:49,830 --> 00:16:51,390
So when we are separating.

252
00:16:51,820 --> 00:16:53,770
So this is the common thing.

253
00:16:54,110 --> 00:16:57,280
OK, this part is common in both the linked list.

254
00:16:57,290 --> 00:17:01,870
So when we are separating the length of these two linked list, so this part will get deleted.

255
00:17:02,620 --> 00:17:07,030
OK, so the differences basically do only so and minus mistal.

256
00:17:07,540 --> 00:17:12,220
Now what is the value, what is the significance of this to let's call this the.

257
00:17:12,790 --> 00:17:17,710
OK, so this is basically the difference between the difference of the lines between the two linked

258
00:17:17,710 --> 00:17:18,040
list.

259
00:17:18,250 --> 00:17:26,079
OK, let's call the OK now this is the big list B, so what we will do, we will make we will jump two

260
00:17:26,079 --> 00:17:26,920
steps ahead.

261
00:17:27,290 --> 00:17:30,050
OK, so we will jump two steps ahead.

262
00:17:30,070 --> 00:17:33,150
So first to jump and the second jump.

263
00:17:33,580 --> 00:17:36,130
So basically we are here.

264
00:17:36,220 --> 00:17:38,590
OK, so we are standing at this point.

265
00:17:40,550 --> 00:17:42,230
We are standing at this point.

266
00:17:42,770 --> 00:17:49,100
OK, now what we will do so this is a and this is where we are currently standing.

267
00:17:49,170 --> 00:17:55,740
OK, so these other two points now what we will do, we will move ahead in both the list.

268
00:17:56,210 --> 00:17:58,370
OK, now these two points.

269
00:17:59,400 --> 00:18:05,760
Point this one point to an end point victory, both these points are equidistant from the intersection

270
00:18:05,760 --> 00:18:06,090
point.

271
00:18:06,660 --> 00:18:15,120
OK, so both Evan and Bitly, they are equidistant from the intersection point while they are equidistant

272
00:18:15,120 --> 00:18:22,110
because the difference was to OK, their defense was to and in the bigger list, I made two jumps.

273
00:18:23,530 --> 00:18:24,760
Now, there's no difference.

274
00:18:24,840 --> 00:18:31,120
OK, we are standing at equidistant from seven now, we will move ahead in both the linked list, so

275
00:18:31,120 --> 00:18:33,880
I will move ahead then move ahead.

276
00:18:34,330 --> 00:18:34,960
Move ahead.

277
00:18:34,960 --> 00:18:37,480
And here will be our intersection point.

278
00:18:39,990 --> 00:18:46,920
OK, so the approach is very simple, so step one, find the length of both the linked list finding

279
00:18:47,140 --> 00:18:47,930
about the list.

280
00:18:48,270 --> 00:18:53,000
Second, the defense of the link list take different.

281
00:18:53,790 --> 00:18:55,830
Third step, move ahead.

282
00:18:57,310 --> 00:19:04,830
EnLink list be OK, I'm assuming BS the bigger list, so move ahead and be how much we have to move

283
00:19:05,070 --> 00:19:05,670
defense.

284
00:19:06,420 --> 00:19:09,660
OK, now fourth point, they are equidistant.

285
00:19:09,670 --> 00:19:13,110
OK, so both the points are equidistant.

286
00:19:14,840 --> 00:19:16,340
From the intersection point.

287
00:19:17,350 --> 00:19:21,220
And the fifth step is to move ahead in both the linked list.

288
00:19:22,950 --> 00:19:28,920
Move ahead in both things list, either you will get the intersection point, all these new intersection

289
00:19:28,920 --> 00:19:29,880
points, then we will return.

290
00:19:30,240 --> 00:19:34,130
OK, so I'm assuming that mailing list is bigger one.

291
00:19:34,410 --> 00:19:37,310
So if the mailing list is bigger, then I will lose SREP.

292
00:19:37,820 --> 00:19:39,840
OK, now let us write the code.

293
00:19:40,980 --> 00:19:45,070
So first of all, let us first write a function to find the list.

294
00:19:45,090 --> 00:19:45,510
OK.

295
00:19:47,150 --> 00:19:48,230
So I have a function.

296
00:19:51,970 --> 00:19:55,390
Learned what it will take, it will take at least.

297
00:20:00,670 --> 00:20:06,910
It will take the heart of the list and it will return the land, so initially the ground zero.

298
00:20:08,970 --> 00:20:10,800
OK, so now let's say.

299
00:20:11,730 --> 00:20:14,670
So while help is not a cold tunnel.

300
00:20:17,240 --> 00:20:18,650
We have to look on placeless.

301
00:20:20,690 --> 00:20:24,530
And then head Equis next of head.

302
00:20:30,000 --> 00:20:31,230
And then they will return.

303
00:20:32,410 --> 00:20:32,890
Count.

304
00:20:33,730 --> 00:20:38,980
OK, so this is our land function and our time complexity of this land function is when.

305
00:20:39,320 --> 00:20:40,720
OK, now.

306
00:20:42,040 --> 00:20:48,970
What we discussed, we will find the length of both the linked list, so M is basically.

307
00:20:53,510 --> 00:20:55,070
The length of the first list.

308
00:20:58,070 --> 00:21:00,890
And is the length of the second longest.

309
00:21:03,620 --> 00:21:08,210
Now we have to take the difference, OK, so defense.

310
00:21:09,460 --> 00:21:10,690
Absolute function.

311
00:21:11,680 --> 00:21:14,850
I am taking the absolute function because I don't know which one is bigger.

312
00:21:14,890 --> 00:21:17,050
OK, and let's do.

313
00:21:17,050 --> 00:21:17,830
And my him.

314
00:21:19,110 --> 00:21:23,280
You can do a minus and also so absolute minus our would will be positive.

315
00:21:23,350 --> 00:21:23,680
OK.

316
00:21:23,970 --> 00:21:29,600
The significance of absolute now since we assumed that Lent that linked list is bigger.

317
00:21:30,180 --> 00:21:31,780
So I'm checking my assumption here.

318
00:21:31,800 --> 00:21:36,320
So if Mr. Thanin, then we will simply Swabian be OK?

319
00:21:38,110 --> 00:21:46,370
We will simply step in and be now basically at this point, we can safely say BS, good, OK, BS,

320
00:21:46,450 --> 00:21:48,760
a bigger list now if we have to do.

321
00:21:49,780 --> 00:21:54,140
So as we can see here, we have to move ahead and be OK.

322
00:21:54,160 --> 00:21:55,840
How much more weight difference?

323
00:21:57,560 --> 00:21:59,780
So the defense was so.

324
00:22:00,780 --> 00:22:07,440
Their defense was basically an DayQuil zero less in the and I placeless.

325
00:22:08,820 --> 00:22:14,700
I have to move baby steps ahead in the second link list, submissively vehicles next of me.

326
00:22:16,830 --> 00:22:19,470
Now, at this point, what is the scenario?

327
00:22:20,930 --> 00:22:29,270
Both boat and they are equidistant from the intersection point and we are equidistant from the intersection

328
00:22:29,270 --> 00:22:29,630
point.

329
00:22:29,660 --> 00:22:30,020
OK.

330
00:22:32,520 --> 00:22:36,920
Symbol, now, what we have to do, we will move ahead in both the linked list.

331
00:22:38,170 --> 00:22:40,820
OK, so while it is not a question.

332
00:22:43,360 --> 00:22:44,170
And simply.

333
00:22:45,170 --> 00:22:46,580
These Nordquist tunnel.

334
00:22:47,680 --> 00:22:49,680
I have to move ahead in both the list.

335
00:22:49,780 --> 00:22:54,820
OK, so if it was close by, that means the intersection point.

336
00:22:55,390 --> 00:23:00,330
So if it is intersection point, we can simplify it and way we can simplify it and be OK.

337
00:23:01,120 --> 00:23:04,030
Otherwise A equals next of.

338
00:23:06,590 --> 00:23:09,110
And B equals the next of B.

339
00:23:12,640 --> 00:23:18,280
Now, if development, that means there is no intersection, so we will simply tunnel.

340
00:23:18,340 --> 00:23:21,730
OK, now let's run our code and then we will submit.

341
00:23:23,720 --> 00:23:25,430
OK, so line number 72.

342
00:23:28,740 --> 00:23:29,580
OK, so.

343
00:23:34,440 --> 00:23:36,240
OK, so now let's submit.

344
00:23:41,290 --> 00:23:48,360
OK, so we're going to get some now see the difference first eight milliseconds, then 76 millisecond.

345
00:23:48,370 --> 00:23:51,040
And this is our latest submission, 44 milliseconds.

346
00:23:51,820 --> 00:23:53,740
And you can also see the memory.

347
00:23:53,830 --> 00:23:54,170
OK.

348
00:23:54,400 --> 00:23:55,650
Sixteen point nine memory.

349
00:23:56,350 --> 00:23:58,270
Now, let us do so.

350
00:23:58,270 --> 00:23:58,960
In this case.

351
00:23:58,960 --> 00:24:00,130
Where is the time complexity?

352
00:24:04,270 --> 00:24:12,880
So first, this land function, it will take time and again when time, then we are moving ahead basically

353
00:24:12,880 --> 00:24:13,600
all the time.

354
00:24:14,200 --> 00:24:20,080
And then in the worst case, when there's no intersection, it will take, let's say, basically let

355
00:24:20,080 --> 00:24:21,030
us assume on time.

356
00:24:21,040 --> 00:24:22,990
So basically the time complexity is linear.

357
00:24:23,260 --> 00:24:29,980
OK, and blessin time, complexity is linear and space complexities or when we are not using any extra

358
00:24:29,980 --> 00:24:30,340
space.

359
00:24:30,640 --> 00:24:33,130
OK, so this is the best solution we have.

360
00:24:34,520 --> 00:24:36,570
OK, this is the best solution.

361
00:24:36,830 --> 00:24:44,450
So this was here, the time complexity was Emman and the space complexity was open and in this case,

362
00:24:44,750 --> 00:24:47,120
the time complexity was linear, basically one.

363
00:24:47,630 --> 00:24:51,770
And the space complexity, it was due to the map we have created.

364
00:24:51,800 --> 00:24:56,030
OK, so this was Letwin and this is our best solution.

365
00:24:56,060 --> 00:25:03,200
OK, time complexity is linear and the space complexities on OK, so this is how we can solve this problem.

366
00:25:03,680 --> 00:25:06,750
OK, now there is one more way to solve this problem.

367
00:25:07,580 --> 00:25:09,920
So the fourth we we will not implement this way.

368
00:25:10,220 --> 00:25:13,880
But I'm just giving you a lot of idea that there also exist a fourth.

369
00:25:13,890 --> 00:25:17,350
We know how we can solve this problem.

370
00:25:17,360 --> 00:25:21,440
So even if you do and let's say this is even Seattle.

371
00:25:22,130 --> 00:25:24,080
So again, B1, B2.

372
00:25:25,110 --> 00:25:32,430
Vetri, and then she went on to do OK, so what we will do, we will start from me when we will reach

373
00:25:32,430 --> 00:25:36,240
the end of the linked list and after reaching the end, we will save this node.

374
00:25:36,510 --> 00:25:40,380
OK, so we will save this node and then.

375
00:25:41,580 --> 00:25:45,310
I will make and I will make a second I will make a loop in the linked list.

376
00:25:45,370 --> 00:25:49,950
OK, so what I will do, I will simply do 020 next equals.

377
00:25:50,370 --> 00:25:51,750
OK, so this was a.

378
00:25:52,680 --> 00:25:55,650
So now we have a loop in the list.

379
00:25:55,770 --> 00:25:57,480
OK, now there is a problem.

380
00:25:58,200 --> 00:26:00,030
The cycle in the linked list.

381
00:26:00,120 --> 00:26:03,840
OK, Newtek cycle in list.

382
00:26:04,830 --> 00:26:09,750
OK, so this is a very famous problem, I will also solve this problem, so the technical analyst,

383
00:26:09,750 --> 00:26:10,830
this is a famous problem.

384
00:26:11,100 --> 00:26:11,430
OK.

385
00:26:11,460 --> 00:26:13,900
So with the help of this problem, if you have solved this problem.

386
00:26:14,280 --> 00:26:20,730
So what we will do, we will be able to find this even OK, with the help of this problem, we will

387
00:26:20,730 --> 00:26:22,470
be able to find Siwan.

388
00:26:22,530 --> 00:26:24,210
OK, so this is our list.

389
00:26:24,510 --> 00:26:25,680
We will start from BE1.

390
00:26:26,070 --> 00:26:31,500
And if you have solved this problem, you can understand that we will be able to find even.

391
00:26:31,720 --> 00:26:36,300
OK, if you do not know this problem, if you are unaware of this problem, then do not worry.

392
00:26:36,300 --> 00:26:37,800
I will solve this problem later on.

393
00:26:37,830 --> 00:26:42,780
OK, but here I just want to tell you that this is a very famous problem.

394
00:26:43,140 --> 00:26:45,880
And with the help of this problem, they will be able to find even.

395
00:26:45,970 --> 00:26:51,050
OK, now what we will do after finding this, even after we have the result.

396
00:26:51,570 --> 00:26:55,470
So what we have to do, we have to remove this loop, OK?

397
00:26:55,470 --> 00:26:57,600
We have to remove this link, OK?

398
00:26:57,600 --> 00:27:01,770
Because the problem it mentioned clearly that we do not have to change the original structure of the

399
00:27:01,770 --> 00:27:04,050
problem, original structure of the linked list.

400
00:27:04,350 --> 00:27:06,840
OK, that's why I saved you two here.

401
00:27:06,990 --> 00:27:09,810
OK, so that we can do to do it, Aaron.

402
00:27:09,810 --> 00:27:10,990
Next is null.

403
00:27:11,680 --> 00:27:19,620
OK, now after we know the solution of the problem, after we get to the seven, we will lose you to

404
00:27:19,620 --> 00:27:23,520
our next question so that the structure of the list do not changes.

405
00:27:24,720 --> 00:27:26,500
So the structure of English do not change.

406
00:27:26,520 --> 00:27:28,710
OK, because this was a requirement of the problem.

407
00:27:29,880 --> 00:27:31,800
OK, now.

408
00:27:32,740 --> 00:27:34,150
Let's OK.

409
00:27:34,170 --> 00:27:37,450
So if the question was detect if there is any intersection point.

410
00:27:37,720 --> 00:27:41,560
OK, now the question was you have to simply return true or false.

411
00:27:44,790 --> 00:27:50,920
OK, you have to return to the return type of the problem is bull and the problem is very simple detect

412
00:27:50,970 --> 00:27:52,080
intersection point.

413
00:27:54,030 --> 00:27:58,530
Basically redaction problem, OK, we have to detect the intersection point now, there are dueling

414
00:27:58,530 --> 00:28:03,120
lists, even you and she wants you to see three.

415
00:28:05,080 --> 00:28:10,690
This is between me to be three, and she wants you to see three.

416
00:28:11,220 --> 00:28:16,090
Now, the problem that we have solved that problem, ask us to find the seven.

417
00:28:16,450 --> 00:28:19,480
But now what I'm trying to say here is you have to return.

418
00:28:19,480 --> 00:28:20,230
True or false.

419
00:28:20,500 --> 00:28:21,910
OK, you have to return.

420
00:28:21,910 --> 00:28:23,650
True or do you have to return false?

421
00:28:23,680 --> 00:28:27,160
Basically, you have to detect whether to intercept or not.

422
00:28:27,910 --> 00:28:32,290
OK, so one base you can use the above approach that we have discussed.

423
00:28:32,770 --> 00:28:34,270
OK, but since.

424
00:28:35,460 --> 00:28:39,210
It doesn't ask us to find out even then why we should find someone.

425
00:28:39,250 --> 00:28:44,550
OK, we simply have to detect whether to north intercept, whether to intercept or not.

426
00:28:44,880 --> 00:28:47,430
So what I will do, I will start.

427
00:28:48,120 --> 00:28:51,570
So this is a I will reach the end point of it.

428
00:28:51,820 --> 00:28:54,120
OK, so the end point of is three.

429
00:28:55,770 --> 00:29:02,970
Then what I will do, I will start from B, this is B, and then I will reach the end point of B, so

430
00:29:02,970 --> 00:29:04,390
then point of B is C three.

431
00:29:04,980 --> 00:29:13,890
Now, if the end point, if the tale of A is same as the tale of B, that means there is intersection,

432
00:29:13,890 --> 00:29:16,320
otherwise there is no intersection.

433
00:29:17,500 --> 00:29:18,320
OK, simple.

434
00:29:18,330 --> 00:29:19,920
You can also take this an example.

435
00:29:19,920 --> 00:29:25,790
One, two and this is five and similarly selected three, four and five.

436
00:29:26,220 --> 00:29:32,010
So in this case, the end point of the first list is five and similarly the end of the second linked

437
00:29:32,010 --> 00:29:33,150
list is also five.

438
00:29:33,570 --> 00:29:40,230
OK, so if the end point of both the same this intersection, if then if the end points are different,

439
00:29:40,230 --> 00:29:41,370
there is no intersection.

440
00:29:41,580 --> 00:29:43,050
OK, very simple problem.

441
00:29:43,860 --> 00:29:44,260
OK.

442
00:29:44,370 --> 00:29:49,060
So in this case, what you have to do is start from the first linked list, reach that point, start

443
00:29:49,060 --> 00:29:52,370
from the second list which then point event for the simplest intersection.

444
00:29:52,380 --> 00:29:59,160
So the time complexity will be linear and pleasant and basically the space complexity will be constant

445
00:29:59,160 --> 00:29:59,430
space.

446
00:29:59,460 --> 00:30:00,600
OK, or one space.

447
00:30:01,470 --> 00:30:03,210
So I hope you got the idea of this problem.

448
00:30:03,210 --> 00:30:05,610
If you have any doubt in this problem, you can ask me.

449
00:30:06,760 --> 00:30:07,150
OK.

450
00:30:08,200 --> 00:30:08,650
Thank you.

