Finding the Intersection Point of Two Linked Lists

so let's continue with our playlist and before that hey everyone welcome back to the channel I hope you guys are doing extremely well so the problem that we will be solving today is finding the intersection point of a given y link list so what is the problem exactly stating it's stating that it'll be given two link list so basically head one and head two so if I look at the first link list this one is the first link list if I look at the second link list this is the second link list now your task is to Fig figure out the first Common node can I say this entire portion is the common portion between the first link list and the second link list so this is the first Common node this is the second common node and the third common node so your task is to return the first Common node or the first intersecting point of two given link list but you might be thinking hey what if they never Collide what if you given an example something like this this can be a link list and then I can can have another link list something like this they're never colliding it's not a y link list in this case you'll be returning null stating that they never Collide in case they Collide then you will be returning the first node got it so if this problem comes up in an interview we will be starting off with the extreme n solution and what will be that can I say this that I'm looking for a node which is in the link list one and which is in the link list two so can I do this I will go through the first link list and probably memorize the notes that I've seen or that are there in the link list one just remember in your memory somewhere and then what you'll do is you will again Traverse the second link list and if you see any node which you memorized has been visited again that means this is your first point how can you memorize things how can you store it yes we will be using using the concept of hashing very very important concept so what I can do is I can declare a map data structure and I can store the node the entire node as the key do not store the value please why because if you see a four here there is a four here as well so if you store the values it will be wrong instead of it try to store the node and along with it maybe you can store IND your bullion whatever you wish to do let's take two variables temp one and temp two where temp one will be at the starting point of Link list one and temp two will be at the starting point of Link list two let's probably Traverse the first link list so what I'll do is I'll start traving so whatever is the first node let's put it over here and say one and then move it whatever is your second node again put it and move let's go to the next we have four let's try to put it and move let's again take this six and put it and move let's take two and put it and move and then temporary will reach null the moment you reach null that means the traversal on the first link list is completed once once it is completed what I can do is I can probably take this temporary off and I'll do the traversal of the second link list so after the first traversal all the notes of the link list one has been stored in into the map data structure now your next job is to go through the second link list and check if there's a repeating node or not so let's do it we over here is this particular node in the map data structure we don't have it yes we have a node with value one we have it but that is this node that is why I said please store the entire node got it so it is not there let's move to the next when I move to the next it is it is also not there in the map let's move to the next this one is not there in the map let's move to the next this one is not there on the map let's move to the next and we will see that this exact same node is over here in the map if it is there and while traversing the first node which is repeating will be your first point of intersection so what you can do is you can stop over here and you can straight away return in case you Traverse you Traverse and you end up teaching null that means they were separate link list and you did not find an intersecting point got it so this will be the simple hashing method so let's quickly write down the pseudo code in case you want the C++ Java python or JavaScript code all the links will be in the description initially we will be taking a map data structure which will be storing a node and an integer right after that you'll be taking a temporary placing it at the head one okay and let's Traverse on the first link list which is basically till it reaches null and let's say map map dop or whatever according to your language hey map can you store this entire node not the data entire node and after that you ask temp hey can you move ahead temp do next perfect this is my first traversal which will basically store all the notes in your memory let's do the second traversal I can say temporary will be head again but this time head to let's do a traversal again so temp is not equal to null and I will be traversing what will I check I will check hey ma'am do you have this probably find whatever according to your language hey M do you have this temporary if he says yes I do have it yes I do have it that means this is your first repeating node which means means this is your inter intersection Point return this particular temp perfect or else you can straight away go to the next node which is temporary of next end this one and if the entire traversal is completed and you never executed this if statement which means yes there were no common or repeating or intersection Point thereby I will end up returning null what will be the time comp lexity can I say that the first Trav will be taking B of n into whatever time your map takes if your map takes logarithmic it will be n login if your map takes constant time it will be n into one depends on your map's time complexity I've discussed this uh I've discussed this in depth in the hashing lecture go back and watch it again the same thing over here beo of N2 probably this will be N1 N2 into if your map is taking logarithmic if your map is taking B one depend depends on that so can I say that the overall time complexity will be B of N1 into on the map plus b of N2 into whatever the map takes logarithmic n or B of one depending on what language are you using what kind of map you're using what will be the space complexity if I'm going through the first link list and storing everything it'll be B off N1 if I go through the second link list and store everything it will B off N2 depending on which link list you're storing like in our example we took this entire link list and we stored it thereby the space used will be B of N1 you could have done in the opposite manner you could have stored this entire one and then you could have Trav in this one depending on that it doesn't matter because what if in the worst case you might have same length link this so it doesn't matter so this will be your time complexity and the space complexity now this is where the interviewer will not be happy because we're using an external space to store these things we'll ask you to optimize this so we need to optimize the space complexity now this gives me an idea that hey you cannot store the nodes you need to solve it during the traversal itself can I solve it during the traversal okay if T1 is standing here which is the head one and if T2 is standing here can I straight away draw a comparison I cannot I cannot because this is the shorter link list and this is the longer link list can I can I do a comparison I cannot for comparison to happen T2 should stand here and I should compare them and then move T1 here and T2 here compare them move T1 and T2 here and the comparison will succeed but they need to be standing at the same vertical level I cannot stand two steps behind and have a comparison done stand two steps be two steps okay can I move T2 by two steps and make it stand here and then start start the comparison and then start the comparison and then do the comparison can I do this yes I can so my goal will be to make sure whichever is the longer link list whichever is the longer link list I will make sure it goes in in the same level as the shorter one I try to do that how can I do that let's say T1 let's take T2 okay let's first Travers in the first link list and compute the length of that link list so N1 can be taken as zero T1 moves 1 T1 moves 2 T1 moves 3 T1 moves 4 T1 moves 5 T1 moves reaches null So eventually the length of the link list is five can I do the same for this one I can and what will be the length s so when T2 will reach here the length will be seven you can simply Traverse in both both the link list and find out the length once you done for the length what is the next JW can I say one of them will definitely be larger if they equal it's fine you just start if they equal you start comparing but if they're not equal which is in this case N1 is 5 N2 is 7 what is the difference N2 minus N1 two two is the difference if the difference is two what you will do is you will take T2 and make it move by D steps one step two step now T2 stands at the same level as T1 does T1 is at head standing at the same level once you have done this now you can do a simultaneous movement T1 not equal not equal do a simultaneous movement is it equal not equal do a simultaneous movement is is it equal yes it is equal stop then and there and say that this is my Collision note and you can straight away return it quite simple isn't it so can I write down the code I can maybe I can take T1 to be head and I can take N1 to be zero and I can take T2 to be head and N2 to be zero let's do traversal to compute the length which is T1 is not equal to null and you can say N1 ++ and T1 can go to T1 nextt very simple at the same time you can do it for the second link list as well let's move it and you can do N2 ++ and T2 can go to t2. next Once you figured out the length what is your next job the next job is to make sure that the longer link list Travers the remaining distance right so can I say hey what if N1 is smaller than N2 in that case the link list two will Travers right so maybe maybe I can write a function where I say Collision point of I need to find it of head one head 2 and I'm assuming I'm assuming that this is the greater link list this is the greater link list and this is the smaller one because that is what I'm writing over here and I'm saying please cover a distance of N2 minus N1 please cover a distance of N2 minus N1 and find me out the Collision point and find me out the Collision point or else I will say he return Collision point of this time the smaller is head two the L CL two is the smaller and can be equal as well head one and N1 minus N2 so what I've done is I've written down a function Collision point which takes the smaller which takes the greater and it also takes the distance that you have to Traverse right and either of them will return you the Collision point so I need to write a function Collision point that is accepting a smaller link list head that is accepting a larger link list head and the difference of distance between them right so if I go back what do I need to write I need to write a function which starts at the larger linklist covers the D steps covers the D steps once it is aligned once it is aligned starts comparing starts comparing and the moment it Compares and finds the same it returns that Collis part otherwise it will reach null otherwise it will simultaneously reach null got it so let's quickly write down the function Collision Point Collision Point can be written as it'll take a smaller link list head so maybe I can say small head or small or maybe let's call it temporary one let's take temporary 2 and D perfect what is the first thing the larger will go at the same level so let's move a d steps while D D minus minus and T2 equal to T2 do next so now T1 and T2 are at the same level let's start comparing if they are same I will stop there and there if they're same I will stop otherwise I will keep moving them otherwise I'll keep moving them D1 goes to t1. next and T2 goes to t2. next and whenever they meet they will somehow meet if they're not colliding it will be null and null will be equal to null so you will be returning T1 or T2 whichever you want to return you can because you can return any one of them because the Y Loop will only terminate when they're equal they can be equal at a colliding node or they can be equal at a null so you can return straight away so this will be a collision point and either head one is the smaller and head 2 is the larger or the opposite depending on that this function will execute for both of them you don't have to write repeating lines of code got that so time to discuss the time complexity this is taking beo of N1 this is taking beo of N2 for sure because I'm traversing the entire linklist in order to find out the length after that this D is nothing but B go of N2 minus N1 assum and is greater assuming because that is how much it will Traverse after that I'm doing another while loop how much will this be let's go back to the example I'm standing over here I will end up traversing these notes in case it doesn't collides which is basically the shorter length which is basically the shorter length so I can say another beo of N1 so I have to write it as B go of N1 plus b go of N2 plus b go of N2 - N1 plus b go of N1 minus N1 + N1 goes so it's B go of N1 + 2 N2 can I write this I can so this will be my time complexity and the space complexity will be big of one because I'm not using any external space this is where the interviewer will not be happy with this time complexity and he will ask you to optimize it so the optimal approach will not be using any fancy algorithm rather we will be traving through the link list and we will find out a way to find the common intersection Point let's see how we need to Traverse both the link list together so we will be taking temporary one and temporary 2 remember we will not alter the head we will take two separate variables temporary one placed at the head one of the link list one temporary two placed at the head two of the link list two got it after that we will simultaneously move them one one one place that is basically Travers together temporary one will go here at the same time temporary 2 will go here temporary 1 will go here at the same time temporary 2 will go here after that temporary one will go here temporary 2 will go here at the same time temporary 1 will go here and temporary 2 will go here stop here stop okay and I will erase everything so you stop at a point when you reach the last note why because after this movement temporary one will reach null temporary one will reach null so remember whenever you're traversing and any of the pointers any of the pointers reaches null you will not take it to null instead instead you will take temporary one to Second head opposite the other link list head so you'll basically say temporary one go to the head of the other one so temporary one will be over here and you will move temporary to as it is so this is how the movement will look like after the step I'll I'll explain you why again keep moving them one step one step Next Step will be temporary one will move one temporary two will move two places sorry one place after that again do the same temporary one moves here and temporary 2 will go to the Head one why why because temporary two was going to be null and if you remember I told you while traversing if anyone reaches null it goes to the opposite as temporary one went to the opposite temporary two will also go to the opposite just take them to the opposite perfect if you carefully observe what has happened now is they are aligned they're aligned on the same isn't it let's perform the next steps but before that I'll erase this again take them one step together so temporary one will be here and temporary 2 will be here again take them one step together temporary one is here temporary 2 is here the first point of contact the first point of similarity is where you will say that this is the repeating node or this is the first node where my intersection starts and you straight away return this node uh why does it work I'll be giving you a proof but as of now understand that we Travers and if the temporary one reaches the null we take it to the opposite link list if temporary two reaches the null we take it to the opposite and then move it let's talk about some edge cases before I move on to the code so if you look at the example that we did take the length of L1 was not equivalent to the L length of L2 and that is the reason T1 which is basically temporary one that we took at head one and temporary 2 that we took at head two they were traversing in a different manner what does it mean temporary one reached the last node before the temporary two did why because there was a difference of length there was a difference of length of two that is why T1 reached the last node and then you basically took it to the opposite end when it reached the last door that is what you did but what if the length of both the link list are same what will happen in that case you can keep T1 here T2 here let's Traverse T1 and T2 will Traverse simultaneously D1 and D2 will Trav simultaneously D1 and D2 will Trav simultaneously D1 and D2 will Trav simultaneously and if You observe they will collide they will not reach the end you don't need to move them to the opposite heads they will collide and this will be your intersection point so if length is equal you don't need to do the opposite you you you don't have to write uh separate conditions for it what I'm trying to explain is in case they are of same length it will collide before you move to the end got it if there is a collision Point obviously let's look at one more example we have L1 and we have L2 they're never colliding right so if they're not colliding how do we figure out that we need to stop traversing because they're not colliding there's no Collision note how do we stop let's understand how the algorithm works over here we take a temporary one place it at the head of the link one we take a temporary 2 place it at the head of the link two let's start traversing T1 and T2 will simultaneously move one place right then again T1 and T2 will simultaneously move one place at this moment when T1 moves to null you say hey go to the opposite head go to the opposite head so T1 will be here and T2 will move so T1 moves to the front and T2 will move here perfect I'll just Erase this after this again they will be moving simultaneously T1 moves here T2 moves here after that again they will move simultaneously T1 moves here and T2 moves to the opposite head and if you carefully observe they're again aign they are again aligned same thing happened over here as well the same thing is happening over here as well let's try moving there T1 and T2 will move together T1 and T2 will move together if you carefully observe they have reached the last node they have reached the last node does it mean that you again take them to the opposite heads does it mean that no you will not take it to the opposite head rather you will say hey both of them are at their last note if I move them one step they will reach null if I move them one step they will reach null which means both of them collided simultaneously and have reached null which means there is no Collision point which means there is no Collision Point got it you might be thinking hey what is the proof how are they aligning I will come to that let's first write down the code get the algorithm or get this traversal into your head and then will understand why is that happening because it is very very simple don't worry so I will be writing down the pseudo code in case you want the C++ Java python or JavaScript code all the links will be in the description so what will we be given we will be given head one and head two right what is the first step Ed Case what if the first link list is empty it cannot collide with anyone or what if the second link list is empty same thing it cannot collide so it will never have a collision point so we can return null apart from that we have to write down the code can I say I will take a temporary one and place it at head one I will take a temporary two and place it at head two and we can Trav probably let's leave down the while condition for afterwards what are we doing we basically doing temporary 1 equal to Temporary 1 next and we saying temporary 2 temporary 2. next this is what we are doing right and we know one thing if if if this temporary one while traving just assume just imagine T1 was here and we know after traversing it will reach the null I cannot take it to null I'll have to take it to the opposite head I'll have to take it to the opposite head so what I will write is if after traversal if after traval by any chance it has moved on to the null in that case I will say hey T1 can you basically go to the opposite head that is head of two the same thing can I write for T2 hey T2 while traversing if you have reached null if you have reached null can you go to the opposite head which is head one perfect am I messing out on an case yes while traversing what if they collide they might Collide I will say hey if T1 appears to be T2 same at the same node then this is my Collision point you can return T1 or T2 perfect how I written down all the hge cases probably I have so we need to think about the exit conditions right so what are the exit conditions uh in terms of collision I'm very sure that this will be my exit condition if it collides the notes will be same and I will exit can I say that if there is no Collision if there is no Collision in that case there will be a point when T2 will reach null and T1 will reach null and null will be equal to null null will be equal to null because that is what I'm writing if this is equal to this and I will be returning null so both the exit conditions are satisfied if they Collide fine if they do not Collide they will reach null so what will be the exit condition am I missing out on in case I am look at these conditions rather look at these lines what am I doing T1 goes to the next T2 goes to the next so when I'm starting off I'm not checking the first note I'm not checking the first note what if you're given a link list which looks something like this and I'm saying this is my head one and this is my head two it's the same link list find me the Collision point the first head will be the Collision point the first head will be the colliding point so what I can say is hey maybe I can just write T1 not equal to T2 just for the sake of it because just in case it's for the first time because after that this will take care but just in case it is for the first time in that case I will end up returning T1 or T2 because they are the same notes the same starting point apart from that it will never be executed why because the code will get terminated over here it will get terminated over here got it so we have seen the code now it's time to understand that why are temp one and temp 2 aligning at the same level load after some steps of traversal let's understand it T1 initially is at head 1 T2 initially is at head 2 what is the difference between them if I say the difference is D can I say it is two why because I need to take two steps in order to reach T1 T2 is two steps behind T1 understood let's perform the algorithm T1 and T2 moves simultaneously to the next node T1 and T2 again moves simultaneously to the next note T1 and T2 again moves simultaneously to the next note T1 and T2 again moves simultaneously to the next node and this is happening because of these two lines right after that what will happen again T1 will move to the next and T2 will move to the next let's let's erase all of these things now whenever T1 reaches null so whenever T1 reaches null what happens let's analyze you said T1 equal to t1. next it will reach null right after that it will go ahead and check if it is null if it is null it ends up going to head two it it ends up going to head two but if before that let's visualize something how many steps is T2 behind T1 1 two it is still two steps behind T1 so T1 goes here goes to the opposite head so can I say T2 is still two steps behind right and T1 is at the head which is still two steps behind this particular place right what happens T2 takes one step Takes Two Step whenever it reaches null it means it will reach here it means it will reach here which means T2 will take two steps to reach here and that's how many T1 will take that is why they align the proof is very simple since you're moving them simultaneously T2 is bound to be same number of steps behind whenever T1 reaches the opposite head so after this you again move T1 and T2 T2 reaches here covers up and then T2 reaches here T1 reaches here here means here so hence the line because it was D steps behind you you made sure that this D1 goes to the opposite so that you can cover that D steps that is the proof behind this algorithm so what will be the time complexity for this particular algorithm can I say B go of N1 plus N2 why can I see that we took T1 right we took T2 now this is the case when it never collided how much did T1 Traverse it went from here to here then from here to here then from here to here then from here to here then from here to here then from here to here how much did T2 Traverse from here to here from here to here from here to here from here to here and from here to here eventually T2 will move here and they stopped so ultimately T1 will Traverse each of the nodes of the both length list which means N1 plus N2 and after that whenever it reaches null T2 will be at null and T1 will be at null and they will collide and it will stop so it ends up touching every possible node thereby the time complexity is N1 + N2 and the space complexity is B go of one so let's quickly get back into the code editor and check out the code so you given the first head and the second head I'll write down the edge case after that the same code that I've written on the iPad and if you hit the submit button this will be accepted the Java code is pretty much similar and you can find out the python and JavaScript code links in the description and if you're still watching I'm very sure that You' have understood the brute the better and the optimal approach and if that is the case please please do consider giving us a like and if you're new to our Channel what are you waiting for hit that subscribe button and with this I'll be wrapping up this video Let's Wait in some of video till then bye-bye take care when heart is broken don't ever forget your golden I will find the light

so let&#39;s continue with our playlist and before that hey everyone welcome back to the channel I hope you guys are doing extremely well so the problem that we will be solving today is finding the intersection point of a given y link list so what is the problem exactly stating it&#39;s stating that it&#39;ll be given two link list so basically head one and head two so if I look at the first link list this one is the first link list if I look at the second link list this is the second link list now your task is to Fig figure out the first Common node can I say this entire portion is the common portion between the first link list and the second link list so this is the first Common node this is the second common node and the third common node so your task is to return the first Common node or the first intersecting point of two given link list but you might be thinking hey what if they never Collide what if you given an example something like this this can be a link list and then I can can have another link list something like this they&#39;re never colliding it&#39;s not a y link list in this case you&#39;ll be returning null stating that they never Collide in case they Collide then you will be returning the first node got it so if this problem comes up in an interview we will be starting off with the extreme n solution and what will be that can I say this that I&#39;m looking for a node which is in the link list one and which is in the link list two so can I do this I will go through the first link list and probably memorize the notes that I&#39;ve seen or that are there in the link list one just remember in your memory somewhere and then what you&#39;ll do is you will again Traverse the second link list and if you see any node which you memorized has been visited again that means this is your first point how can you memorize things how can you store it yes we will be using using the concept of hashing very very important concept so what I can do is I can declare a map data structure and I can store the node the entire node as the key do not store the value please why because if you see a four here there is a four here as well so if you store the values it will be wrong instead of it try to store the node and along with it maybe you can store IND your bullion whatever you wish to do let&#39;s take two variables temp one and temp two where temp one will be at the starting point of Link list one and temp two will be at the starting point of Link list two let&#39;s probably Traverse the first link list so what I&#39;ll do is I&#39;ll start traving so whatever is the first node let&#39;s put it over here and say one and then move it whatever is your second node again put it and move let&#39;s go to the next we have four let&#39;s try to put it and move let&#39;s again take this six and put it and move let&#39;s take two and put it and move and then temporary will reach null the moment you reach null that means the traversal on the first link list is completed once once it is completed what I can do is I can probably take this temporary off and I&#39;ll do the traversal of the second link list so after the first traversal all the notes of the link list one has been stored in into the map data structure now your next job is to go through the second link list and check if there&#39;s a repeating node or not so let&#39;s do it we over here is this particular node in the map data structure we don&#39;t have it yes we have a node with value one we have it but that is this node that is why I said please store the entire node got it so it is not there let&#39;s move to the next when I move to the next it is it is also not there in the map let&#39;s move to the next this one is not there in the map let&#39;s move to the next this one is not there on the map let&#39;s move to the next and we will see that this exact same node is over here in the map if it is there and while traversing the first node which is repeating will be your first point of intersection so what you can do is you can stop over here and you can straight away return in case you Traverse you Traverse and you end up teaching null that means they were separate link list and you did not find an intersecting point got it so this will be the simple hashing method so let&#39;s quickly write down the pseudo code in case you want the C++ Java python or JavaScript code all the links will be in the description initially we will be taking a map data structure which will be storing a node and an integer right after that you&#39;ll be taking a temporary placing it at the head one okay and let&#39;s Traverse on the first link list which is basically till it reaches null and let&#39;s say map map dop or whatever according to your language hey map can you store this entire node not the data entire node and after that you ask temp hey can you move ahead temp do next perfect this is my first traversal which will basically store all the notes in your memory let&#39;s do the second traversal I can say temporary will be head again but this time head to let&#39;s do a traversal again so temp is not equal to null and I will be traversing what will I check I will check hey ma&#39;am do you have this probably find whatever according to your language hey M do you have this temporary if he says yes I do have it yes I do have it that means this is your first repeating node which means means this is your inter intersection Point return this particular temp perfect or else you can straight away go to the next node which is temporary of next end this one and if the entire traversal is completed and you never executed this if statement which means yes there were no common or repeating or intersection Point thereby I will end up returning null what will be the time comp lexity can I say that the first Trav will be taking B of n into whatever time your map takes if your map takes logarithmic it will be n login if your map takes constant time it will be n into one depends on your map&#39;s time complexity I&#39;ve discussed this uh I&#39;ve discussed this in depth in the hashing lecture go back and watch it again the same thing over here beo of N2 probably this will be N1 N2 into if your map is taking logarithmic if your map is taking B one depend depends on that so can I say that the overall time complexity will be B of N1 into on the map plus b of N2 into whatever the map takes logarithmic n or B of one depending on what language are you using what kind of map you&#39;re using what will be the space complexity if I&#39;m going through the first link list and storing everything it&#39;ll be B off N1 if I go through the second link list and store everything it will B off N2 depending on which link list you&#39;re storing like in our example we took this entire link list and we stored it thereby the space used will be B of N1 you could have done in the opposite manner you could have stored this entire one and then you could have Trav in this one depending on that it doesn&#39;t matter because what if in the worst case you might have same length link this so it doesn&#39;t matter so this will be your time complexity and the space complexity now this is where the interviewer will not be happy because we&#39;re using an external space to store these things we&#39;ll ask you to optimize this so we need to optimize the space complexity now this gives me an idea that hey you cannot store the nodes you need to solve it during the traversal itself can I solve it during the traversal okay if T1 is standing here which is the head one and if T2 is standing here can I straight away draw a comparison I cannot I cannot because this is the shorter link list and this is the longer link list can I can I do a comparison I cannot for comparison to happen T2 should stand here and I should compare them and then move T1 here and T2 here compare them move T1 and T2 here and the comparison will succeed but they need to be standing at the same vertical level I cannot stand two steps behind and have a comparison done stand two steps be two steps okay can I move T2 by two steps and make it stand here and then start start the comparison and then start the comparison and then do the comparison can I do this yes I can so my goal will be to make sure whichever is the longer link list whichever is the longer link list I will make sure it goes in in the same level as the shorter one I try to do that how can I do that let&#39;s say T1 let&#39;s take T2 okay let&#39;s first Travers in the first link list and compute the length of that link list so N1 can be taken as zero T1 moves 1 T1 moves 2 T1 moves 3 T1 moves 4 T1 moves 5 T1 moves reaches null So eventually the length of the link list is five can I do the same for this one I can and what will be the length s so when T2 will reach here the length will be seven you can simply Traverse in both both the link list and find out the length once you done for the length what is the next JW can I say one of them will definitely be larger if they equal it&#39;s fine you just start if they equal you start comparing but if they&#39;re not equal which is in this case N1 is 5 N2 is 7 what is the difference N2 minus N1 two two is the difference if the difference is two what you will do is you will take T2 and make it move by D steps one step two step now T2 stands at the same level as T1 does T1 is at head standing at the same level once you have done this now you can do a simultaneous movement T1 not equal not equal do a simultaneous movement is it equal not equal do a simultaneous movement is is it equal yes it is equal stop then and there and say that this is my Collision note and you can straight away return it quite simple isn&#39;t it so can I write down the code I can maybe I can take T1 to be head and I can take N1 to be zero and I can take T2 to be head and N2 to be zero let&#39;s do traversal to compute the length which is T1 is not equal to null and you can say N1 ++ and T1 can go to T1 nextt very simple at the same time you can do it for the second link list as well let&#39;s move it and you can do N2 ++ and T2 can go to t2. next Once you figured out the length what is your next job the next job is to make sure that the longer link list Travers the remaining distance right so can I say hey what if N1 is smaller than N2 in that case the link list two will Travers right so maybe maybe I can write a function where I say Collision point of I need to find it of head one head 2 and I&#39;m assuming I&#39;m assuming that this is the greater link list this is the greater link list and this is the smaller one because that is what I&#39;m writing over here and I&#39;m saying please cover a distance of N2 minus N1 please cover a distance of N2 minus N1 and find me out the Collision point and find me out the Collision point or else I will say he return Collision point of this time the smaller is head two the L CL two is the smaller and can be equal as well head one and N1 minus N2 so what I&#39;ve done is I&#39;ve written down a function Collision point which takes the smaller which takes the greater and it also takes the distance that you have to Traverse right and either of them will return you the Collision point so I need to write a function Collision point that is accepting a smaller link list head that is accepting a larger link list head and the difference of distance between them right so if I go back what do I need to write I need to write a function which starts at the larger linklist covers the D steps covers the D steps once it is aligned once it is aligned starts comparing starts comparing and the moment it Compares and finds the same it returns that Collis part otherwise it will reach null otherwise it will simultaneously reach null got it so let&#39;s quickly write down the function Collision Point Collision Point can be written as it&#39;ll take a smaller link list head so maybe I can say small head or small or maybe let&#39;s call it temporary one let&#39;s take temporary 2 and D perfect what is the first thing the larger will go at the same level so let&#39;s move a d steps while D D minus minus and T2 equal to T2 do next so now T1 and T2 are at the same level let&#39;s start comparing if they are same I will stop there and there if they&#39;re same I will stop otherwise I will keep moving them otherwise I&#39;ll keep moving them D1 goes to t1. next and T2 goes to t2. next and whenever they meet they will somehow meet if they&#39;re not colliding it will be null and null will be equal to null so you will be returning T1 or T2 whichever you want to return you can because you can return any one of them because the Y Loop will only terminate when they&#39;re equal they can be equal at a colliding node or they can be equal at a null so you can return straight away so this will be a collision point and either head one is the smaller and head 2 is the larger or the opposite depending on that this function will execute for both of them you don&#39;t have to write repeating lines of code got that so time to discuss the time complexity this is taking beo of N1 this is taking beo of N2 for sure because I&#39;m traversing the entire linklist in order to find out the length after that this D is nothing but B go of N2 minus N1 assum and is greater assuming because that is how much it will Traverse after that I&#39;m doing another while loop how much will this be let&#39;s go back to the example I&#39;m standing over here I will end up traversing these notes in case it doesn&#39;t collides which is basically the shorter length which is basically the shorter length so I can say another beo of N1 so I have to write it as B go of N1 plus b go of N2 plus b go of N2 - N1 plus b go of N1 minus N1 + N1 goes so it&#39;s B go of N1 + 2 N2 can I write this I can so this will be my time complexity and the space complexity will be big of one because I&#39;m not using any external space this is where the interviewer will not be happy with this time complexity and he will ask you to optimize it so the optimal approach will not be using any fancy algorithm rather we will be traving through the link list and we will find out a way to find the common intersection Point let&#39;s see how we need to Traverse both the link list together so we will be taking temporary one and temporary 2 remember we will not alter the head we will take two separate variables temporary one placed at the head one of the link list one temporary two placed at the head two of the link list two got it after that we will simultaneously move them one one one place that is basically Travers together temporary one will go here at the same time temporary 2 will go here temporary 1 will go here at the same time temporary 2 will go here after that temporary one will go here temporary 2 will go here at the same time temporary 1 will go here and temporary 2 will go here stop here stop okay and I will erase everything so you stop at a point when you reach the last note why because after this movement temporary one will reach null temporary one will reach null so remember whenever you&#39;re traversing and any of the pointers any of the pointers reaches null you will not take it to null instead instead you will take temporary one to Second head opposite the other link list head so you&#39;ll basically say temporary one go to the head of the other one so temporary one will be over here and you will move temporary to as it is so this is how the movement will look like after the step I&#39;ll I&#39;ll explain you why again keep moving them one step one step Next Step will be temporary one will move one temporary two will move two places sorry one place after that again do the same temporary one moves here and temporary 2 will go to the Head one why why because temporary two was going to be null and if you remember I told you while traversing if anyone reaches null it goes to the opposite as temporary one went to the opposite temporary two will also go to the opposite just take them to the opposite perfect if you carefully observe what has happened now is they are aligned they&#39;re aligned on the same isn&#39;t it let&#39;s perform the next steps but before that I&#39;ll erase this again take them one step together so temporary one will be here and temporary 2 will be here again take them one step together temporary one is here temporary 2 is here the first point of contact the first point of similarity is where you will say that this is the repeating node or this is the first node where my intersection starts and you straight away return this node uh why does it work I&#39;ll be giving you a proof but as of now understand that we Travers and if the temporary one reaches the null we take it to the opposite link list if temporary two reaches the null we take it to the opposite and then move it let&#39;s talk about some edge cases before I move on to the code so if you look at the example that we did take the length of L1 was not equivalent to the L length of L2 and that is the reason T1 which is basically temporary one that we took at head one and temporary 2 that we took at head two they were traversing in a different manner what does it mean temporary one reached the last node before the temporary two did why because there was a difference of length there was a difference of length of two that is why T1 reached the last node and then you basically took it to the opposite end when it reached the last door that is what you did but what if the length of both the link list are same what will happen in that case you can keep T1 here T2 here let&#39;s Traverse T1 and T2 will Traverse simultaneously D1 and D2 will Trav simultaneously D1 and D2 will Trav simultaneously D1 and D2 will Trav simultaneously and if You observe they will collide they will not reach the end you don&#39;t need to move them to the opposite heads they will collide and this will be your intersection point so if length is equal you don&#39;t need to do the opposite you you you don&#39;t have to write uh separate conditions for it what I&#39;m trying to explain is in case they are of same length it will collide before you move to the end got it if there is a collision Point obviously let&#39;s look at one more example we have L1 and we have L2 they&#39;re never colliding right so if they&#39;re not colliding how do we figure out that we need to stop traversing because they&#39;re not colliding there&#39;s no Collision note how do we stop let&#39;s understand how the algorithm works over here we take a temporary one place it at the head of the link one we take a temporary 2 place it at the head of the link two let&#39;s start traversing T1 and T2 will simultaneously move one place right then again T1 and T2 will simultaneously move one place at this moment when T1 moves to null you say hey go to the opposite head go to the opposite head so T1 will be here and T2 will move so T1 moves to the front and T2 will move here perfect I&#39;ll just Erase this after this again they will be moving simultaneously T1 moves here T2 moves here after that again they will move simultaneously T1 moves here and T2 moves to the opposite head and if you carefully observe they&#39;re again aign they are again aligned same thing happened over here as well the same thing is happening over here as well let&#39;s try moving there T1 and T2 will move together T1 and T2 will move together if you carefully observe they have reached the last node they have reached the last node does it mean that you again take them to the opposite heads does it mean that no you will not take it to the opposite head rather you will say hey both of them are at their last note if I move them one step they will reach null if I move them one step they will reach null which means both of them collided simultaneously and have reached null which means there is no Collision point which means there is no Collision Point got it you might be thinking hey what is the proof how are they aligning I will come to that let&#39;s first write down the code get the algorithm or get this traversal into your head and then will understand why is that happening because it is very very simple don&#39;t worry so I will be writing down the pseudo code in case you want the C++ Java python or JavaScript code all the links will be in the description so what will we be given we will be given head one and head two right what is the first step Ed Case what if the first link list is empty it cannot collide with anyone or what if the second link list is empty same thing it cannot collide so it will never have a collision point so we can return null apart from that we have to write down the code can I say I will take a temporary one and place it at head one I will take a temporary two and place it at head two and we can Trav probably let&#39;s leave down the while condition for afterwards what are we doing we basically doing temporary 1 equal to Temporary 1 next and we saying temporary 2 temporary 2. next this is what we are doing right and we know one thing if if if this temporary one while traving just assume just imagine T1 was here and we know after traversing it will reach the null I cannot take it to null I&#39;ll have to take it to the opposite head I&#39;ll have to take it to the opposite head so what I will write is if after traversal if after traval by any chance it has moved on to the null in that case I will say hey T1 can you basically go to the opposite head that is head of two the same thing can I write for T2 hey T2 while traversing if you have reached null if you have reached null can you go to the opposite head which is head one perfect am I messing out on an case yes while traversing what if they collide they might Collide I will say hey if T1 appears to be T2 same at the same node then this is my Collision point you can return T1 or T2 perfect how I written down all the hge cases probably I have so we need to think about the exit conditions right so what are the exit conditions uh in terms of collision I&#39;m very sure that this will be my exit condition if it collides the notes will be same and I will exit can I say that if there is no Collision if there is no Collision in that case there will be a point when T2 will reach null and T1 will reach null and null will be equal to null null will be equal to null because that is what I&#39;m writing if this is equal to this and I will be returning null so both the exit conditions are satisfied if they Collide fine if they do not Collide they will reach null so what will be the exit condition am I missing out on in case I am look at these conditions rather look at these lines what am I doing T1 goes to the next T2 goes to the next so when I&#39;m starting off I&#39;m not checking the first note I&#39;m not checking the first note what if you&#39;re given a link list which looks something like this and I&#39;m saying this is my head one and this is my head two it&#39;s the same link list find me the Collision point the first head will be the Collision point the first head will be the colliding point so what I can say is hey maybe I can just write T1 not equal to T2 just for the sake of it because just in case it&#39;s for the first time because after that this will take care but just in case it is for the first time in that case I will end up returning T1 or T2 because they are the same notes the same starting point apart from that it will never be executed why because the code will get terminated over here it will get terminated over here got it so we have seen the code now it&#39;s time to understand that why are temp one and temp 2 aligning at the same level load after some steps of traversal let&#39;s understand it T1 initially is at head 1 T2 initially is at head 2 what is the difference between them if I say the difference is D can I say it is two why because I need to take two steps in order to reach T1 T2 is two steps behind T1 understood let&#39;s perform the algorithm T1 and T2 moves simultaneously to the next node T1 and T2 again moves simultaneously to the next note T1 and T2 again moves simultaneously to the next note T1 and T2 again moves simultaneously to the next node and this is happening because of these two lines right after that what will happen again T1 will move to the next and T2 will move to the next let&#39;s let&#39;s erase all of these things now whenever T1 reaches null so whenever T1 reaches null what happens let&#39;s analyze you said T1 equal to t1. next it will reach null right after that it will go ahead and check if it is null if it is null it ends up going to head two it it ends up going to head two but if before that let&#39;s visualize something how many steps is T2 behind T1 1 two it is still two steps behind T1 so T1 goes here goes to the opposite head so can I say T2 is still two steps behind right and T1 is at the head which is still two steps behind this particular place right what happens T2 takes one step Takes Two Step whenever it reaches null it means it will reach here it means it will reach here which means T2 will take two steps to reach here and that&#39;s how many T1 will take that is why they align the proof is very simple since you&#39;re moving them simultaneously T2 is bound to be same number of steps behind whenever T1 reaches the opposite head so after this you again move T1 and T2 T2 reaches here covers up and then T2 reaches here T1 reaches here here means here so hence the line because it was D steps behind you you made sure that this D1 goes to the opposite so that you can cover that D steps that is the proof behind this algorithm so what will be the time complexity for this particular algorithm can I say B go of N1 plus N2 why can I see that we took T1 right we took T2 now this is the case when it never collided how much did T1 Traverse it went from here to here then from here to here then from here to here then from here to here then from here to here then from here to here how much did T2 Traverse from here to here from here to here from here to here from here to here and from here to here eventually T2 will move here and they stopped so ultimately T1 will Traverse each of the nodes of the both length list which means N1 plus N2 and after that whenever it reaches null T2 will be at null and T1 will be at null and they will collide and it will stop so it ends up touching every possible node thereby the time complexity is N1 + N2 and the space complexity is B go of one so let&#39;s quickly get back into the code editor and check out the code so you given the first head and the second head I&#39;ll write down the edge case after that the same code that I&#39;ve written on the iPad and if you hit the submit button this will be accepted the Java code is pretty much similar and you can find out the python and JavaScript code links in the description and if you&#39;re still watching I&#39;m very sure that You&#39; have understood the brute the better and the optimal approach and if that is the case please please do consider giving us a like and if you&#39;re new to our Channel what are you waiting for hit that subscribe button and with this I&#39;ll be wrapping up this video Let&#39;s Wait in some of video till then bye-bye take care when heart is broken don&#39;t ever forget your golden I will find the light

Transcript for:Finding the Intersection Point of Two Linked Lists

Transcript for:
Finding the Intersection Point of Two Linked Lists