1
00:00:02,220 --> 00:00:02,910
Hi, everyone.

2
00:00:02,940 --> 00:00:08,550
So in today's video, we are going to solve this question, remove get an order from the end of the

3
00:00:08,550 --> 00:00:09,150
linked list.

4
00:00:09,480 --> 00:00:13,420
So let me explain the question and then we will discuss about the possible solution.

5
00:00:13,740 --> 00:00:15,430
So this is these are the notes.

6
00:00:15,870 --> 00:00:22,090
So one, two, three, four, five, six, seven, eight, nine and 10.

7
00:00:22,410 --> 00:00:24,400
So there are total ten nodes, right.

8
00:00:25,320 --> 00:00:28,010
So basically the length of my list is ten.

9
00:00:28,440 --> 00:00:31,810
So this is length of linked list is basically ten.

10
00:00:32,220 --> 00:00:38,220
Right now, what I want to say is so OK, so first let's discuss before moving.

11
00:00:38,370 --> 00:00:40,250
Let us try to find the key.

12
00:00:40,800 --> 00:00:45,960
OK, so if you are able to find the gate and order from the end, then we can also be done with.

13
00:00:45,990 --> 00:00:52,170
So first, let's discuss how we can find a decade or so, for example, let's say the value of KS for.

14
00:00:52,320 --> 00:00:53,880
So what is the fourth node from then.

15
00:00:53,910 --> 00:00:55,440
So this is the first node from the end.

16
00:00:55,770 --> 00:00:57,040
This is the second last note.

17
00:00:57,060 --> 00:00:57,900
This is the third.

18
00:00:57,900 --> 00:00:58,870
And this is the fourth.

19
00:00:59,190 --> 00:01:01,680
So basically, we want to find this node.

20
00:01:01,730 --> 00:01:06,410
OK, after finding this node, we will remove the original question is a removal.

21
00:01:06,810 --> 00:01:09,840
But first, let's discuss how we can find this node.

22
00:01:09,840 --> 00:01:10,260
Right.

23
00:01:10,740 --> 00:01:12,090
So how we can find this node.

24
00:01:12,090 --> 00:01:13,890
So there is one way.

25
00:01:14,490 --> 00:01:17,100
So the first rule is basically it is very simple.

26
00:01:17,130 --> 00:01:18,800
So first, find out the land.

27
00:01:19,320 --> 00:01:20,720
OK, so what is the land?

28
00:01:20,940 --> 00:01:22,530
So Lento's let's say it is.

29
00:01:22,560 --> 00:01:23,400
All right.

30
00:01:24,000 --> 00:01:26,130
So let's say the land is.

31
00:01:26,130 --> 00:01:32,340
And so any number of nodes present in our linked list and so the value of intestine and after finding

32
00:01:32,340 --> 00:01:32,970
out the end.

33
00:01:33,180 --> 00:01:35,400
So and let's say this is key.

34
00:01:35,400 --> 00:01:38,240
So key is basically the key to node from the end.

35
00:01:38,250 --> 00:01:49,170
So get geared node from end is basically and the minus K plus one net node from front.

36
00:01:50,150 --> 00:01:52,910
OK, so let's try to evaluate what I'm saying.

37
00:01:53,210 --> 00:02:02,570
So I want to see that get a note from the end is Samia's and minus K plus one that note from the friend.

38
00:02:02,820 --> 00:02:06,740
OK, so let's see whether whether this formula is basically correct or not.

39
00:02:06,770 --> 00:02:08,979
So this is the fourth node.

40
00:02:09,590 --> 00:02:11,660
OK, so this is the case for.

41
00:02:11,670 --> 00:02:13,250
So this is the fourth node from the end.

42
00:02:13,940 --> 00:02:15,330
So let's apply the formula.

43
00:02:15,370 --> 00:02:18,860
So 10 minus four, plus one.

44
00:02:19,070 --> 00:02:20,940
So this is seven.

45
00:02:20,960 --> 00:02:23,330
So this should be seventh in order from the start.

46
00:02:23,510 --> 00:02:23,760
OK.

47
00:02:23,780 --> 00:02:29,330
So first and second, third, fourth, fifth, sixth and seventh.

48
00:02:29,480 --> 00:02:32,090
So this is seventh in order from the front.

49
00:02:32,240 --> 00:02:34,430
So that means this formula is correct.

50
00:02:34,640 --> 00:02:44,000
So it is the same as get an order from and is same as and minus cabelas when it node from friend.

51
00:02:44,930 --> 00:02:47,370
Now how did I get to this formula.

52
00:02:47,390 --> 00:02:49,490
So basically this simple math formula.

53
00:02:49,490 --> 00:02:49,790
Right.

54
00:02:50,150 --> 00:02:51,230
This is simple math.

55
00:02:51,230 --> 00:02:56,600
Or if you don't know the formula then it is, I mean you can just observe and you can derive this formula.

56
00:02:56,630 --> 00:02:58,790
OK, so this is very simple math.

57
00:02:59,120 --> 00:03:01,940
If you will observe, you can easily reach at this formula.

58
00:03:02,270 --> 00:03:03,710
So how we can find.

59
00:03:04,350 --> 00:03:05,460
So it is very simple.

60
00:03:05,480 --> 00:03:07,040
The first approach says.

61
00:03:08,960 --> 00:03:13,130
So the first approach is step one, find the length of the list.

62
00:03:13,610 --> 00:03:18,900
We know how to find the little interest, just outraged over the compelling encounter.

63
00:03:19,400 --> 00:03:22,100
So after step one, what is step two?

64
00:03:22,370 --> 00:03:26,450
So step two is basically calculate what will calculate.

65
00:03:26,570 --> 00:03:30,400
So you will calculate this value and minus K plus one.

66
00:03:30,860 --> 00:03:36,110
So you know the value of N so and is basically the length to the number of nodes present gains given

67
00:03:36,110 --> 00:03:37,220
by the user.

68
00:03:37,220 --> 00:03:44,810
And so after calculating this formula, let's say the value of KS for and let's consider this example

69
00:03:44,810 --> 00:03:46,340
only and the value of an instant.

70
00:03:46,370 --> 00:03:48,740
So this formula will came out to be seven.

71
00:03:48,740 --> 00:03:49,170
Right.

72
00:03:49,190 --> 00:03:55,190
So how many iterations you want to do so you have to do let's say this value is basically a OK, so

73
00:03:55,190 --> 00:03:59,490
you will do a minus one iterations at minus one iteration.

74
00:03:59,510 --> 00:04:01,760
Basically you will do six jumps.

75
00:04:03,800 --> 00:04:04,920
You will do six jumps.

76
00:04:04,940 --> 00:04:07,220
Let's see, so this is the first to jump.

77
00:04:07,280 --> 00:04:13,640
This is the second jump start to jump forward to jump with the jump and this is the sixth jump.

78
00:04:13,670 --> 00:04:15,940
OK, so we are doing six jumps.

79
00:04:16,190 --> 00:04:18,950
So after doing six jumps, you will reach at this note.

80
00:04:18,950 --> 00:04:22,880
And that's how we will be able to find the node to find the.

81
00:04:23,450 --> 00:04:25,460
So that's how we will be able to find this node.

82
00:04:25,490 --> 00:04:29,570
OK, so in this approach, what is the time, complexity and the space?

83
00:04:29,570 --> 00:04:30,380
Complexity, time?

84
00:04:30,380 --> 00:04:31,190
Complexity is big.

85
00:04:31,190 --> 00:04:35,160
Often we are just finding out the length and iterating over the list again.

86
00:04:35,300 --> 00:04:35,720
Right.

87
00:04:35,870 --> 00:04:38,090
And again, the space complexity is constrained.

88
00:04:38,120 --> 00:04:39,780
We are using constant extra space.

89
00:04:40,370 --> 00:04:43,250
OK, so we are traversing the link list two times.

90
00:04:43,310 --> 00:04:45,090
First, when we are finding out the length.

91
00:04:45,320 --> 00:04:48,080
And second, when we are finding out the node.

92
00:04:48,080 --> 00:04:49,610
So we are doing to travel.

93
00:04:50,000 --> 00:04:50,420
Right.

94
00:04:50,810 --> 00:04:56,370
But the question is, you have to do only one traversal, only one traversal is allowed.

95
00:04:57,620 --> 00:05:02,610
Now the question is, how are we going to solve this question when only one traversal is allowed?

96
00:05:03,020 --> 00:05:04,010
So let's see.

97
00:05:06,100 --> 00:05:08,390
So it is very simple problem, but will do.

98
00:05:08,450 --> 00:05:11,890
So let's take this example, only 10 notes the value of case four.

99
00:05:11,930 --> 00:05:14,530
OK, so we have a..

100
00:05:15,640 --> 00:05:23,440
First, second, third, fourth, fifth, sixth, seventh, eighth, ninth and tenth, so the value

101
00:05:23,450 --> 00:05:30,160
of an assault case for successful means, this is the first word from the end, the second note from

102
00:05:30,160 --> 00:05:31,790
the entire north from the end and the fourth.

103
00:05:31,880 --> 00:05:33,330
Also, I want to find this now.

104
00:05:33,370 --> 00:05:33,790
Right.

105
00:05:34,760 --> 00:05:37,240
OK, so only one traversal is allowed.

106
00:05:37,240 --> 00:05:40,540
We can traverse over the long list only once and not twice.

107
00:05:40,570 --> 00:05:42,680
OK, that means the above approach will not work.

108
00:05:42,700 --> 00:05:45,330
OK, so tell us when the vessel is allowed.

109
00:05:45,550 --> 00:05:51,390
So the approach is basically take two pointers, take two pointers.

110
00:05:52,390 --> 00:05:54,210
So let's call it pointer one.

111
00:05:54,820 --> 00:05:59,800
OK, this is your pointer and this is your pointer to the name.

112
00:05:59,800 --> 00:06:03,240
The name of the first pointer is when the second point is to find.

113
00:06:03,670 --> 00:06:06,780
Now what you will do is basically there's a trick involved here.

114
00:06:07,090 --> 00:06:09,820
So what will the value of KS for?

115
00:06:09,880 --> 00:06:13,230
So maintain the distance between one and two pointer by four.

116
00:06:13,240 --> 00:06:17,040
So that means make to pointer will jump four steps.

117
00:06:17,080 --> 00:06:20,680
OK, so take four steps so two will come here.

118
00:06:20,710 --> 00:06:25,480
First step, second step, third step and fourth step.

119
00:06:25,660 --> 00:06:27,360
So this is your position of two.

120
00:06:28,660 --> 00:06:30,070
So I'm repeating myself again.

121
00:06:30,100 --> 00:06:34,420
So initially when it's presented to you, it's also present at the head.

122
00:06:34,460 --> 00:06:36,640
OK, so initially this is my head of the list.

123
00:06:36,970 --> 00:06:40,760
So when it was present at the head of the linked list, now the value of Gaisford.

124
00:06:40,780 --> 00:06:47,680
So what we will do so take point number two and it will take OK, it will take jumps.

125
00:06:48,930 --> 00:06:57,210
Now, this is to OK, after taking the case for and this is one, how much is the difference between

126
00:06:57,210 --> 00:06:57,750
one and two?

127
00:06:57,750 --> 00:06:59,690
So one, two, three and four.

128
00:06:59,700 --> 00:07:03,420
So the difference between one and two is basically four nodes.

129
00:07:03,420 --> 00:07:03,780
Right?

130
00:07:04,470 --> 00:07:06,450
So the differences for node perfect.

131
00:07:06,810 --> 00:07:12,240
Now, what we will do, so one will move ahead in this direction to really move ahead in this direction.

132
00:07:12,270 --> 00:07:13,290
OK, so this is null.

133
00:07:14,340 --> 00:07:18,430
So the idea is when two will reach at this point.

134
00:07:18,780 --> 00:07:23,300
So when two will reach at null, there will be one president.

135
00:07:23,310 --> 00:07:25,320
So one will present four nodes back.

136
00:07:25,350 --> 00:07:28,650
So that means so first node second or third and fourth.

137
00:07:28,860 --> 00:07:32,100
So one will be present at this node when two will regional.

138
00:07:32,880 --> 00:07:34,170
OK, and one means.

139
00:07:34,320 --> 00:07:36,800
So this is the node that we want to find.

140
00:07:37,560 --> 00:07:38,980
So the steps is very simple.

141
00:07:39,000 --> 00:07:40,230
So what is the first step?

142
00:07:40,480 --> 00:07:42,660
Take two points, one and two.

143
00:07:42,990 --> 00:07:44,930
Initially they will be present at the head.

144
00:07:45,600 --> 00:07:54,390
Now the second step is basically the two pointer will make jumps, the two points will make the jumps.

145
00:07:54,600 --> 00:08:00,330
And now the difference between the pointer to end point seven is basically off key.

146
00:08:00,450 --> 00:08:01,970
Guignard Fine.

147
00:08:02,460 --> 00:08:06,180
Now what we will do so move one and two simultaneously.

148
00:08:07,260 --> 00:08:11,430
One and two will simultaneously move in forward direction rate.

149
00:08:11,790 --> 00:08:12,950
So we have single list.

150
00:08:13,020 --> 00:08:14,670
We can only move forward addiction.

151
00:08:14,970 --> 00:08:16,970
So both will move in the forward direction.

152
00:08:16,980 --> 00:08:25,710
And step number four when two will reach and then so one will reach the node that we want to find basically

153
00:08:25,710 --> 00:08:26,650
the desired node.

154
00:08:27,390 --> 00:08:28,890
So let's take this example only.

155
00:08:28,900 --> 00:08:30,810
So one is here and two is here.

156
00:08:32,640 --> 00:08:34,620
OK, so let's do one thing.

157
00:08:34,620 --> 00:08:39,179
Let's try this let's try this logic on this example.

158
00:08:39,179 --> 00:08:39,530
Right.

159
00:08:39,809 --> 00:08:40,990
So we have 10 nodes.

160
00:08:41,669 --> 00:08:51,160
So this is nor one nor two, three, four, five, six, seven, eight, nine and ten.

161
00:08:51,180 --> 00:08:52,670
And finally, we have nine.

162
00:08:54,570 --> 00:08:58,540
So there is one present, so one and two, initially, they both are retired.

163
00:08:58,570 --> 00:09:01,740
OK, so this is my one and this is my two.

164
00:09:02,190 --> 00:09:10,440
Now two will do jumps and the value of KS for OK, so first to jump, second, jump, jump and fall

165
00:09:10,440 --> 00:09:10,800
to jump.

166
00:09:10,980 --> 00:09:12,840
So this is the position of two.

167
00:09:13,410 --> 00:09:13,860
Fine.

168
00:09:14,130 --> 00:09:17,100
Now both one and two will move forward.

169
00:09:17,130 --> 00:09:19,830
OK, so let's move them forward simultaneously.

170
00:09:20,100 --> 00:09:21,100
So remove the.

171
00:09:21,540 --> 00:09:26,010
So this is OK and remove this will move forward.

172
00:09:26,040 --> 00:09:28,530
So who is moving forward.

173
00:09:29,490 --> 00:09:30,900
One is moving forward.

174
00:09:32,350 --> 00:09:33,610
Who is moving forward?

175
00:09:34,660 --> 00:09:45,010
One is moving forward, two is moving forward and one is moving forward, two is moving forward and

176
00:09:45,010 --> 00:09:52,090
one is moving forward to two regional two is moving forward and one is moving forward.

177
00:09:52,390 --> 00:09:55,690
Now, as soon as your two reaches none.

178
00:09:56,590 --> 00:09:58,750
So one will reach at this node.

179
00:09:58,750 --> 00:09:59,710
And what is this node?

180
00:09:59,740 --> 00:10:06,040
So this is the last node, second or third astronaut and the fourth node from the end.

181
00:10:06,040 --> 00:10:08,630
And this is the node that we want to find out.

182
00:10:08,650 --> 00:10:11,130
OK, so this is our desired node.

183
00:10:12,580 --> 00:10:16,780
So finally went to regional one will be at the desired.

184
00:10:16,780 --> 00:10:20,320
And also finally, what I will do so I will return one.

185
00:10:20,950 --> 00:10:27,510
And via this code is working because the difference between two and one is basically of Kennard's.

186
00:10:27,760 --> 00:10:29,740
So that's why I went to will reach.

187
00:10:29,920 --> 00:10:32,860
The final one will be key nodes behind.

188
00:10:32,860 --> 00:10:39,550
OK, one will be key behind and that's how we will be able to find the gate node from the end and how

189
00:10:39,550 --> 00:10:40,320
much traversal.

190
00:10:40,540 --> 00:10:44,550
So we are doing we are just simply traversing on the link list one time.

191
00:10:44,560 --> 00:10:46,990
OK, so this is only one traversal.

192
00:10:47,890 --> 00:10:50,140
We are not traversing the linked list two times.

193
00:10:50,140 --> 00:10:52,270
We are traversing the linked list only one time.

194
00:10:52,630 --> 00:10:58,950
So again, the time complexity is big off and the space complexity is also big of one.

195
00:10:58,960 --> 00:11:00,010
So space is constrained.

196
00:11:00,010 --> 00:11:03,010
So the time complexity of this matter and the previous matter both has him.

197
00:11:03,190 --> 00:11:09,730
But the only differences we are doing or even traversal in the approach finding out the land approach

198
00:11:10,060 --> 00:11:11,730
there was to traversal.

199
00:11:11,740 --> 00:11:13,740
OK, so here we are using one traversal.

200
00:11:14,020 --> 00:11:16,000
Now let's come back to the original question.

201
00:11:16,210 --> 00:11:18,670
So the original question is not to find out.

202
00:11:19,030 --> 00:11:23,230
The original question is not to find out the gate node from there, and the original question is to

203
00:11:23,230 --> 00:11:25,040
remove the gate and order from then.

204
00:11:25,090 --> 00:11:32,620
OK, so the original question is we have to remove the gate node from then and we have to do this and

205
00:11:32,620 --> 00:11:33,730
one traversal only.

206
00:11:33,970 --> 00:11:35,650
So let's see how we can do this.

207
00:11:35,680 --> 00:11:38,110
So we just have to modify our this approach.

208
00:11:38,440 --> 00:11:44,500
So we just have to modify this approach so how we can modify over this approach.

209
00:11:44,860 --> 00:11:48,580
This is one so one is present at the desired location.

210
00:11:48,580 --> 00:11:49,740
I want to remove this node.

211
00:11:49,960 --> 00:11:56,320
So if you want to delete one node, so suppose this is your linked list.

212
00:11:57,220 --> 00:12:02,020
If you want to delete this node, that means I have to stop at this node.

213
00:12:02,350 --> 00:12:05,710
So I have to stop at this order so that I can do something like this.

214
00:12:06,700 --> 00:12:07,120
Right.

215
00:12:07,300 --> 00:12:12,700
So I have to stop one node before the deciding if this is the node to be deleted.

216
00:12:12,910 --> 00:12:16,240
Then I have to stop one node before the node, which has to delete it.

217
00:12:16,240 --> 00:12:16,630
Right.

218
00:12:16,900 --> 00:12:19,810
So that means we will stop when the reaches.

219
00:12:20,110 --> 00:12:24,310
No, this is not we will stop when he reaches the last node.

220
00:12:24,610 --> 00:12:25,300
These two.

221
00:12:25,320 --> 00:12:27,460
OK, so then two will reach the last node.

222
00:12:27,460 --> 00:12:29,380
So one will be present at this node.

223
00:12:29,380 --> 00:12:33,790
OK, one node behind the note to be deleted and then we can do something like this.

224
00:12:34,490 --> 00:12:36,460
OK, so this node will get deleted.

225
00:12:36,520 --> 00:12:36,940
Right.

226
00:12:37,240 --> 00:12:39,040
So we will just modify this.

227
00:12:39,910 --> 00:12:45,190
So what we have to do so first step will remain same, second step remains same towards the same.

228
00:12:45,190 --> 00:12:49,210
The fourth step will be when two will reach the last node.

229
00:12:49,210 --> 00:12:52,320
And what is the condition of last year or two where next will be null.

230
00:12:53,020 --> 00:12:58,930
So when two will reach the last node, so one will reach one node before the desired node.

231
00:12:59,110 --> 00:13:00,430
So one will reach here.

232
00:13:00,640 --> 00:13:05,590
OK, and then what we can do so we can do one arrow next is basically.

233
00:13:07,700 --> 00:13:09,590
Next of next of kin, right?

234
00:13:11,460 --> 00:13:14,090
We can do we can make this connection right.

235
00:13:14,300 --> 00:13:17,160
So this node will be removed from the linked list.

236
00:13:17,170 --> 00:13:20,070
So we have to modify our solution, right.

237
00:13:20,550 --> 00:13:25,420
OK, so we can do this and we can solve this question in only one traversal.

238
00:13:25,470 --> 00:13:28,430
OK, so similarly, you can update your land approach also.

239
00:13:29,290 --> 00:13:30,940
OK, you can update your land approach.

240
00:13:31,200 --> 00:13:33,020
So what was our land approach?

241
00:13:37,520 --> 00:13:43,250
So Lente approach was first find out the lente, obviously we have to find out the land and then we

242
00:13:43,250 --> 00:13:48,960
have to calculate this Phumla and Mindscape Lasagna's then we were doing AM minus one titrations.

243
00:13:48,980 --> 00:13:51,780
We were doing six jumps to reach the desired node.

244
00:13:51,800 --> 00:13:56,240
So here what we will do instead of five minus one titrations, we will do administrations.

245
00:13:56,600 --> 00:14:02,390
So we will do five jumps so that we can stop one order before the node, which is to be deleted.

246
00:14:02,970 --> 00:14:04,810
We want to delete this not right.

247
00:14:04,820 --> 00:14:09,170
So I will stop at this, at this node and then I will make this connection.

248
00:14:09,380 --> 00:14:12,170
I am minus two iterations so we will do five jumps.

249
00:14:12,170 --> 00:14:12,490
Right.

250
00:14:12,650 --> 00:14:14,180
So you can modify the code.

251
00:14:14,840 --> 00:14:18,650
OK, so let's write the code for removing it from the end of the linked list.

252
00:14:18,650 --> 00:14:19,860
And this is our logic.

253
00:14:20,790 --> 00:14:23,080
OK, so this is our final logic.

254
00:14:23,090 --> 00:14:23,960
Take two points.

255
00:14:23,960 --> 00:14:27,500
One and two waterbird two will make jumps.

256
00:14:28,370 --> 00:14:30,890
One and two will both move in the forward direction.

257
00:14:30,890 --> 00:14:32,890
And this is the stopping right now.

258
00:14:32,930 --> 00:14:37,170
OK, so this is the stopping the idea when the next of two becomes known, that means the last.

259
00:14:37,190 --> 00:14:43,220
And so when will stop one node before the which is related and then we will do this.

260
00:14:43,230 --> 00:14:47,480
OK, so this question is actually present only two, right?

261
00:14:47,710 --> 00:14:48,670
So this is the question.

262
00:14:48,680 --> 00:14:52,430
Remove the net in order from the end of the list and it will see the question.

263
00:14:52,460 --> 00:14:56,590
So it is saying here you have to do this question in one path.

264
00:14:56,600 --> 00:14:58,880
So this one path means only one traversal.

265
00:14:58,880 --> 00:14:59,210
Right.

266
00:14:59,480 --> 00:15:01,450
So we have to do this question one traversal.

267
00:15:02,420 --> 00:15:04,580
OK, so this is the example.

268
00:15:04,610 --> 00:15:06,970
One, two, three, four, five, the value of these two.

269
00:15:06,980 --> 00:15:08,490
So that means I have to remove the node.

270
00:15:08,810 --> 00:15:12,040
So this is the ability link list one, two, three and five.

271
00:15:12,560 --> 00:15:15,600
So instead of let's rename the variable key.

272
00:15:15,680 --> 00:15:17,780
OK, so I want to create a..

273
00:15:18,950 --> 00:15:23,920
So let me write the step so that you can understand what you have to do.

274
00:15:23,930 --> 00:15:25,520
So I will take two pointers.

275
00:15:26,360 --> 00:15:31,160
So pointer one and two initially both represent at the heart of the linked list.

276
00:15:31,730 --> 00:15:32,110
Fine.

277
00:15:32,210 --> 00:15:33,170
So this is step one.

278
00:15:33,500 --> 00:15:37,550
Step two is basically the pointer to will move the jumps.

279
00:15:37,790 --> 00:15:42,530
It will look so that the difference between first and second notice of Gaetjens.

280
00:15:42,530 --> 00:15:42,860
Right.

281
00:15:43,280 --> 00:15:47,270
So the difference between two minus one, this is off key.

282
00:15:47,480 --> 00:15:47,860
Right.

283
00:15:48,110 --> 00:15:53,180
So today's one and two will move in forward direction simultaneously.

284
00:15:53,190 --> 00:15:55,270
So wanting to move forward.

285
00:15:56,750 --> 00:15:59,690
OK, and what is the stopping criteria of moving forward?

286
00:15:59,720 --> 00:16:02,930
So the stopping right is when two will reach the last node.

287
00:16:03,730 --> 00:16:08,330
So we do to add next is basically null.

288
00:16:08,540 --> 00:16:10,490
So when do will reach the last node?

289
00:16:11,060 --> 00:16:15,650
So this is the condition for reaching the last node, then I will stop.

290
00:16:15,660 --> 00:16:18,400
OK, so this is the stopping condition and after that.

291
00:16:18,890 --> 00:16:21,200
So this will be the condition.

292
00:16:21,770 --> 00:16:26,180
OK, so this is one and this is the node which we want to delete.

293
00:16:26,360 --> 00:16:30,410
So I will do I will make a connection like this, so I will do one.

294
00:16:31,160 --> 00:16:35,810
The next one is simply the next of next of one.

295
00:16:37,830 --> 00:16:43,080
And finally, what we will do so if you will see that the function is listed, Alstott, I have to return

296
00:16:43,080 --> 00:16:45,870
the head of the linked list, so finally we will return the head.

297
00:16:45,960 --> 00:16:47,760
OK, so this is our approach.

298
00:16:48,450 --> 00:16:55,350
And the time complexity discussed many times is linear and we are doing only one puzzle when it passes.

299
00:16:56,340 --> 00:16:57,110
So let's see.

300
00:16:57,270 --> 00:16:58,290
Let's write the code.

301
00:16:58,290 --> 00:16:58,610
Right.

302
00:16:59,310 --> 00:17:02,220
So take we have to make two points first.

303
00:17:02,370 --> 00:17:03,720
So Liston would start.

304
00:17:04,730 --> 00:17:05,150
When?

305
00:17:06,599 --> 00:17:09,690
As president and similarly, the second pointed.

306
00:17:11,430 --> 00:17:18,060
You start also this is also President Leithead, OK, so how many jumps he jumps, so we have to do

307
00:17:18,270 --> 00:17:18,569
jumps.

308
00:17:18,630 --> 00:17:23,950
So while guey minus minus so this loop will run good times.

309
00:17:23,970 --> 00:17:24,900
OK, so.

310
00:17:26,869 --> 00:17:28,130
I have to do Ketcham's right?

311
00:17:28,160 --> 00:17:31,730
So this loop will run jumps, so this loop will run.

312
00:17:31,740 --> 00:17:35,190
Sorry, so this Global Times and what we have to do.

313
00:17:35,210 --> 00:17:37,070
So two equals.

314
00:17:38,520 --> 00:17:42,030
Next off, the search is moving forward, correct?

315
00:17:42,570 --> 00:17:44,980
And now one and two will both move forward.

316
00:17:45,030 --> 00:17:47,340
OK, and what is stopping right to do next?

317
00:17:47,340 --> 00:17:47,750
Asmal.

318
00:17:47,970 --> 00:17:56,250
So we have to reach the last 10 or so while to add or next is not a question.

319
00:17:57,060 --> 00:18:01,430
So this is my stomping criteria and both will move forward.

320
00:18:02,040 --> 00:18:04,650
So one equals.

321
00:18:06,560 --> 00:18:10,430
Next up, one and two equals.

322
00:18:12,260 --> 00:18:21,770
Next off, the perfect and finally, so finally, we what we will do, so we will delete it and we will

323
00:18:21,770 --> 00:18:25,950
delete the kid node from end.

324
00:18:27,400 --> 00:18:29,390
OK, so let's delete the node.

325
00:18:29,400 --> 00:18:32,510
So for the leading the node, one arrow next.

326
00:18:33,970 --> 00:18:34,570
Is.

327
00:18:37,630 --> 00:18:39,040
Next off, next of kin.

328
00:18:40,300 --> 00:18:46,210
And after deleting then what we have to do, so I have to return the head of the list, OK, so I have

329
00:18:46,210 --> 00:18:48,340
to return the hair and so I am returning the head.

330
00:18:49,700 --> 00:18:53,200
OK, so I think we did everything fine.

331
00:18:53,620 --> 00:18:55,390
So I think this code should work.

332
00:18:55,390 --> 00:18:57,150
But there is one problem with this code.

333
00:18:57,160 --> 00:18:59,770
So let me run this code and then I will show you what is the problem.

334
00:19:03,630 --> 00:19:05,520
So our is running fine.

335
00:19:06,560 --> 00:19:08,120
But when will submit this?

336
00:19:08,390 --> 00:19:13,290
It will definitely give us a error and I will tell you why that will come.

337
00:19:13,970 --> 00:19:16,920
There is one simple case that we are not considering.

338
00:19:17,840 --> 00:19:18,950
So our court is working.

339
00:19:19,820 --> 00:19:20,260
Yes.

340
00:19:20,270 --> 00:19:23,220
So what we are getting so we are getting runtime error.

341
00:19:23,900 --> 00:19:30,680
OK, so what we are doing here is so this undefined behavior means so this is random, red and white

342
00:19:30,680 --> 00:19:31,700
and tamira you can see.

343
00:19:31,720 --> 00:19:35,820
So this line, what they are doing so you are accessing to do next.

344
00:19:35,900 --> 00:19:38,060
OK, and what if the weasel.

345
00:19:39,170 --> 00:19:42,440
So what if twizzle you are doing null arrow next.

346
00:19:43,360 --> 00:19:46,380
And obviously, this will give you rent, Tamara.

347
00:19:46,450 --> 00:19:51,430
OK, so in what situation this two will be none.

348
00:19:52,720 --> 00:19:53,920
So consider one situation.

349
00:19:53,930 --> 00:19:59,640
So let's say there are five notes in a link list or let's say there are only four notes.

350
00:19:59,650 --> 00:20:01,860
So therefore not in your list.

351
00:20:01,870 --> 00:20:02,290
Right.

352
00:20:02,740 --> 00:20:09,460
And let's say you want to delete the fourth and order from and delete fourth nolde from.

353
00:20:09,480 --> 00:20:12,340
And so this is the first order from the end.

354
00:20:12,370 --> 00:20:15,070
This is the second note from then the third note from then.

355
00:20:15,070 --> 00:20:16,520
And this is the fourth note from then.

356
00:20:16,780 --> 00:20:18,940
So that means I want to delete the first note.

357
00:20:19,070 --> 00:20:27,390
OK, if you apply the formula and minus K plus one so and is for gays also four for minus four plus

358
00:20:27,520 --> 00:20:27,720
one.

359
00:20:27,730 --> 00:20:29,710
So that means the first note from the beginning.

360
00:20:30,020 --> 00:20:34,540
So I want to delete the first note from the beginning and now executable code.

361
00:20:34,570 --> 00:20:38,210
So what we are doing so one and two will put one and two is present here.

362
00:20:38,230 --> 00:20:40,860
So this is your one and this is also your two, right.

363
00:20:41,140 --> 00:20:42,040
Then what you are doing.

364
00:20:42,310 --> 00:20:44,750
So while giving minus minus how many times.

365
00:20:44,770 --> 00:20:46,490
So four times this loop will run.

366
00:20:46,720 --> 00:20:47,650
So one time.

367
00:20:47,960 --> 00:20:50,560
Second time, third time and the fourth time.

368
00:20:50,560 --> 00:20:50,920
So this is.

369
00:20:51,030 --> 00:20:51,600
All right.

370
00:20:52,330 --> 00:20:54,940
So basically your two is pointing towards null.

371
00:20:55,660 --> 00:20:59,380
So your two is pointing towards null and then you are doing null next.

372
00:20:59,410 --> 00:21:04,510
So in this situation, the situation in which the length of the linked list.

373
00:21:04,690 --> 00:21:10,660
So if the length of the list is the same as the then or the value of key, then in that case your two

374
00:21:10,660 --> 00:21:12,500
will become null and you will get married.

375
00:21:12,580 --> 00:21:14,080
Now, how to resolve this problem?

376
00:21:14,230 --> 00:21:14,660
OK.

377
00:21:14,680 --> 00:21:21,250
So think how we can solve this problem, what condition we should add, so we can simply write the condition

378
00:21:21,250 --> 00:21:28,180
here that if basically the pointer too becomes null.

379
00:21:28,840 --> 00:21:33,960
So if BU becomes knowledge that means Gabe becomes equal to the length of the list.

380
00:21:34,090 --> 00:21:36,580
OK, and then in that case what we can do.

381
00:21:36,590 --> 00:21:38,160
So we have to delete that.

382
00:21:38,200 --> 00:21:40,340
OK, so we have to delete the first node.

383
00:21:40,570 --> 00:21:44,620
So in that case we have to delete the first order so we can simply write it down when I do next.

384
00:21:45,550 --> 00:21:49,570
OK, one is pointing towards the first node so we can return one error next.

385
00:21:49,610 --> 00:21:49,980
Fine.

386
00:21:49,990 --> 00:21:50,990
So let's do that.

387
00:21:51,790 --> 00:21:53,170
Let me erase the screen.

388
00:21:54,020 --> 00:21:54,880
OK, so.

389
00:21:58,300 --> 00:22:05,260
Check first that if basically two becomes null if twizzle.

390
00:22:08,020 --> 00:22:16,060
So when this condition will be so, when basically the length of length list is basically close to the

391
00:22:16,060 --> 00:22:16,510
value of.

392
00:22:16,900 --> 00:22:20,740
OK, so in that case, so in that case, what do you have to do?

393
00:22:20,770 --> 00:22:26,250
So you have to delete the head and basically after the first not right.

394
00:22:26,620 --> 00:22:28,760
So for the leading the first nobody can write.

395
00:22:28,780 --> 00:22:32,290
You can write one arrow next.

396
00:22:37,260 --> 00:22:39,210
So we can return when I do next.

397
00:22:39,270 --> 00:22:43,140
OK, so I am returning when I do next door, the function is let's not start.

398
00:22:43,910 --> 00:22:46,980
OK, so now I think our code will work.

399
00:22:47,400 --> 00:22:50,210
OK, so one thing here is so we are not deleting the node.

400
00:22:50,220 --> 00:22:55,710
So our code is basically suffering from memory problem, but that's fine.

401
00:22:56,160 --> 00:23:01,730
Right is fine because we are submitting our code on an online website.

402
00:23:01,770 --> 00:23:04,240
OK, so it's it's ok.

403
00:23:04,290 --> 00:23:06,300
OK, if you want you can handle the memory.

404
00:23:06,570 --> 00:23:08,560
Similarly we have memory like here also.

405
00:23:08,580 --> 00:23:10,290
OK, it's your choice.

406
00:23:10,290 --> 00:23:12,120
If you want to handle the memory leak you can handle.

407
00:23:12,120 --> 00:23:13,310
Otherwise it's also fine.

408
00:23:13,620 --> 00:23:14,850
So let's Amitabha called.

409
00:23:20,430 --> 00:23:26,040
OK, so now this time of accord is working for all the test cases success, and I will call this ninety

410
00:23:26,040 --> 00:23:29,840
two point seven two percent faster than all the zipless resolution.

411
00:23:30,300 --> 00:23:32,180
So that's how our code is working.

412
00:23:32,190 --> 00:23:39,170
And one last time, OK, so we are solving this question in only one hour time.

413
00:23:39,180 --> 00:23:42,840
Complexity is linear and space complexity is constant.

414
00:23:42,840 --> 00:23:43,770
And we are.

415
00:23:45,000 --> 00:23:49,710
And we are solving this question in one post, and you don't need to worry about the value of this,

416
00:23:49,710 --> 00:23:50,120
basically.

417
00:23:50,490 --> 00:23:53,450
OK, so you don't need to worry about gay will always be valid.

418
00:23:53,670 --> 00:23:58,550
So you do not have a conditions like this if gays greater than the length of the list.

419
00:23:58,800 --> 00:24:03,420
So there is no need to write conditions like this because it does give an indication that the case is

420
00:24:03,420 --> 00:24:04,190
going to be valid.

421
00:24:04,200 --> 00:24:07,570
So if I have any doubt in this question, you can ask me.

422
00:24:07,590 --> 00:24:08,370
OK, thank you.

