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.