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.