LeetCode 160. Intersection of Two Linked Lists Solution Explained - Java

[@abhishekkumargupta3043]

LOL! Somebody kill me first. THIS guy's thought process is amazing.

[@Rahulyadav-lv7dh]

We have 1000 of problems in life ,but solving leetcode problem isn't one of them ,thanks to Nick

[@oscaropdyou]

Another approach is to count elements in A and B. And then find out the diff. Move the pointer forward in longer list for diff number of times. Now, we have same number of end elements to compare. Then start comparing values iterating through both lists.

[@melvinkimathi8924]

I tried this on leetcode and it gives a "Time Limit exceeded error"

[@manojkr9198]

I think he talked about this approach in the beginning

[@Noname-sn6ty]

Hash set or map will be even shorter

[@arealist8913]

@@Noname-sn6ty That will be. But the question suggests you do it in O(1) space complexity.

[@AnandKumar-kz3ls]

@@melvinkimathi8924 for me its working in leetcode not giving TLE ListNode *getIntersectionNode(ListNode *headA, ListNode *headB){ int lenA,lenB,cnt; lenA=0; lenB=0; ListNode* tA=headA; ListNode* tB=headB; while(tA){ tA=tA->next; lenA++; } while(tB){ tB=tB->next; lenB++; } cnt=abs(lenA-lenB); if(lenA>lenB){ while(cnt){ headA=headA->next; cnt--; } } else if(lenB>lenA){ while(cnt){ headB=headB->next; cnt--; } } while(headA!=headB){ headA=headA->next; headB=headB->next; } return headA; }

[@raam2508]

You are the Boss Nick !! Some ideas / explanations/ approaches of yours are "Superior" to that of Kevin !!

[@deewademai]

What about on the Example 3 No intersection. a_pointer forever loop of linked-list B. Does the linked-list A ->null = linked-list B -> null? Are those "null" from different linked-list equal?

[@dhineshd94]

have you find it ?

[@hacker-7214]

I wouldve never thought of that. Wtf i feel so stupid.

[@keokawasaki7833]

i feel stupid every fucking minute

[@monikajha3500]

Thank you so much Nick for your efforts. It helps people like me :)

[@kennethso3385]

Why the 1st example 1st intersectVal is not 1 but 8? both linked list the 1 -> 8 -> 4 -> 5

[@josephlee6590]

Wow thanks! I would've never thought of doing it this way.

[@aivancarlostuquero3782]

Any tips how can you come up with these solutions?

[@michaelyao9389]

Just to want to know. Do you come up this idea by yourself in the beginning? It's amazing! @Nick

[@yudhisthirsingh8401]

My goodness, how and when will I start to come up with such solutions! I mean how the hell to think for such an approach man..!!

[@AvishekPaulOnline]

Google.

[@sarthakbhatia7639]

just a doubt: When both lists have no intersection than will it return NULL or be stuck inside a while loop?

[@sarthakbhatia7639]

Ok got the answer

[@sarthakbhatia7639]

It will work for that to

[@karansagar7870]

How it's not going infinite loop?

[@sarthakbhatia7888]

@@karansagar7870 bro just do the dry run first it will reset the null pointer to the head of the first list, similarly for the second list and then a time will come when both will be null so the condition a_pointer!=b_pointer becomes false and it returns a_pointer which contains null, so it works fine

[@prajitbudhathoki4913]

@@sarthakbhatia7888 lol Are u the same dude asking question and answering later

[@tushardudhatra3478]

For example one I think lists intersect at 1 first and then at 8. I don’t know why EVERYONE is ignoring this thing? Am I missing something here? Please help.

[@psthakur1199]

The previous nodes are different for those ones.Check it and we have to return a ListNode.

[@rampage14x13]

you are not looking for intersection of values of the nodes, you are looking for intersections of the nodes themselves, i.e. addresses

[@sophiaatn5339]

@@rampage14x13 this still doesn't make sense to me

[@chinmaykumar7975]

@@sophiaatn5339 the value doesn't matter the intersecting address of node matters here..

[@jugsma6676]

OMG, it wasn't just me thinking this, glad that i saw this comment. i was thinking the same, it would rather first intersect at 1 then only 8. for example first root(r1)= 4->1->8->4->5 and second root(r2)=5->0->1->->8->4->5 the longer will be move one step faster, so r2 becomes 0->1->->8->4->5. Then the first intersecting is Node(1)->...

[@bismeetsingh352]

Wont this give an infinite loop as the pointers keep jumping from one list to another if there is no intersection?

[@jagaya3662]

No, they both reach the Null at the end of the lists at the same time, breaking out of the loop. List A has length a, list b has length b. If there is no intersection, after a+b steps, pointerA will be at the end of B, while pointerB will be at the end of A -> both pointers are at Null, therefore equal, therefore the while-loop isn't executed, ends and function returns Null.

[@TechNikky]

@@jagaya3662 wow, here is one more genius,

[@satyajeetgoswami1911]

Really helpful Nick, Thanks for the simplified explanation.

[@yitingg7942]

Amazing but I just don't understand why it works!

[@Rahulyadav-lv7dh]

It works because both the pointers have to travel the same distance Suppose length of list 1 = 5 length of list 2 = 7 sum of both = 12 list1 become null first after traversing 5 nodes now it is sent to traverse other 7 nodes of list 2 because it has to travel 12 nodes(sum of both lists) and when list 2 becomes null it is made to travel 5 nodes of list 1, because it has to travel same 12 nodes . So at one point they will meet . Its kinda difficult to explain in words but I hope it helps

[@AnandKumar-kz3ls]

what should be its time complexity 2*max(lenA,lenB) ??

[@Alex-yw7sn]

thanks for explanation after watching your video solution seems much understandable

[@keokawasaki7833]

I understand how it works... but I don't understand why it works. help?

[@jagaya3662]

List A has a length of lenA and is a away from the intersection, List B of lenB and is b away from the intersection - with the tail after the intersection being lenT. Now we take pointers pA and pB and they traverse the lists as mentioned. How long does it take for the pointers to hit the intersection point a _second_ time? pA goes through the first part of A (a), to the intersection point, through the rest of the list (lenT), back to the start of B and through b -> so pA moves "a + lenT + b". What does pB? Well the same except it starts with the head of B and goes: "b + lenT + a". So both pointers take the exact same amount of steps to get to the intersection point a second time. This is true even if the "intersection" doesn't actually exists and they both hit Null at the end of the lists at the same step.

[@keokawasaki7833]

@@jagaya3662 Aye cool! thanks mate~! PS. whoever still dont get it.. try some coffee

[@wheresthebeach0138]

@@jagaya3662 That definitely makes sense; I solved it the same way as you described, but there is one edge case I can't wrap my head around. What if we had a scenario where our lists were [1,2,3] and [1,2,3,4,5], with the lists intersecting at 1 (which is the head for both lists). Wouldn't this approach return node with val 3 instead of 1?

[@jagaya3662]

@@wheresthebeach0138Given the intersection node and all following nodes are part of both lists, if the intersection would be the head, both lists would be identical. An "intersection" in this case means 2 lists "merging" at the intersection. Resulting in a kinda-linked list, which has 2 heads but only one tail. Meaning both lists are identical after the intersection, because they literally link to the exact same nodes. So I don't understand your case. The lists cannot be different after the intersection.

[@psn999100]

@@jagaya3662 Amazing Intuitive explanation. Thanks !

[@himanshibaranwal7297]

I want to understand when there is a difference in the no of elements of two linkedlists, how does the line 22 & 28 works. Can someone explain?

[@lucastperez]

If the size is different, the pointers are not going to find the intersection on the first run because when one of the pointers is in the intersection, the other one will either be behind or after it, right? So what he did was that when a pointer reaches the end of a list, it goes back to the head of the _other_ list. Now imagine this: The first list (A) has the intersection at the 3rd node, so it will need 3 steps to get to it. The second (B) list has the intersection at the 5th node, so it will need 5 steps to get to it. When the a_pointer reaches the end of the list, it goes back to the head of B. Now it will need 5 steps to find the intersection again. Basically it needed 8 steps to get there. When the b_pointer reaches the end of the list, it goes back to the head of A, now it will need 3 more steps to find the intersection again, so it needed 8 steps to get there. Since both needed 8 steps to get to the intersection the second time, they will be there at the same time on the second run. So the condition a_pointer != b_pointer will break, and we can return a_pointer (line 35). Since a_pointer and b_pointer are the same thing, we could return either one of them. If there is no intersection, there will be a moment that both pointers will be null, and then the while breaks because null is equal to null, and we return null. If the lists have the same size, this will happen on the first run. If not, it happens on the second run.

[@lucastperez]

I myself made a drawing of two linked lists and iterated it step by step to see it happen. (:

[@himanshibaranwal7297]

@@lucastperez I did that too and finally understood it.

[@kennangaibel7003]

@@lucastperez Dude this comment should have more likes you just made it me understand it thanks!

[@melvinkimathi8924]

@@lucastperez Thanks for the explanation

[@rovaldyapplyrs3918]

Isnt it possible for a linked list to intersect with itself with itself on this solution? For example Linked lista = [1, 8, 1, 4] Linked listb =[2, 3] by the third iteration , apointer would be 1 and b pointer would be 1?

[@theoxfromoutofthebox2965]

Pointer holds the address and not the value...so in the case you mention a pointer is not equal to b pointer.

[@aniruddhashahapurkar9244]

Just a doubt. The time complexity will be greater than O(n), right?

[@jagaya3662]

It would be O(2n) because worst case, both lists are traversed twice. However only the magnitude of n is important, so O(2n) is just O(n).

[@aniruddhashahapurkar9244]

@@jagaya3662 Thanks friend

[@victoriac7257]

Can someone explain why this works even if they are parallel? Is that because both will eventually end up with null and they are equal and would be returned as null?

[@CyberMew]

If they are parallel (assuming you mean they are of same length), then they will both definitely meet in c1 node (since they are moving at same speed). Which means the while condition is evaluated to false and we just return either 1 of the variable.

[@noormaaz]

@@CyberMew how will this logic work if two linkedlist are not intersecting? The while loop will keep on running without intersection.

[@CyberMew]

@@noormaaz that's the beauty of this solution. no matter what, when they reach the end and point to the head of the other linkedlist, both will meet at null. there is no infinite loop. imagine list A has 5 nodes. list B has 8 nodes. both do not intersect. pointer A will traverse 5 + 8 nodes. pointer B will also traverse 8 + 5 nodes. Both will meet at node #14 (null node). and since null == null, the while-loop ends. :)

[@noormaaz]

@@CyberMew ok at some point at a time they will meet thanks👍

[@shyamjitiwari7519]

In first example why they are not intersecting at 1 instead of 8?

[@AshwiniSingh27]

because they aren't comparing the values (values can be anything), they are comparing the nodes (as in memory/pointer).

[@RomanTokarenko]

Quite elegant solution, thanks

[@cyber.valllll]

from leetcode: > Could you write a solution that runs in O(m + n) time? Your solution has O(n+m+X) complexity since you need to traverse the whole list that can be tooooo long. Let's say n = 1, m = 2 and x = 10^5. Instead of 3 operations you would have 3+10^5.

[@TechNikky]

how this approach come to your mind I mean what's the trick to finding the best approach

[@sankaranarayanankm7049]

what if they didnt intersect? why we didn't gave any conditions for that???

[@noormaaz]

how will this logic work if two linkedlist are not intersecting? The while loop will keep on running without intersection.

[@iconliving9076]

Thanks but why do you look so uninterested?

[@arpitamandal1472]

How to build logic like yours?

[@AvishekPaulOnline]

Google

[@Dineshkumar-uz4dw]

Can we use unordered set to store the node and check the second linked list?? Or we can't store node in set?? I'm getting error when I use unordered set pls help

[@ruchiray8557]

Thank you so much you are amazing

[@venkyvids]

Please help me understand the flaw in my logic. I've iterated LinkedList A till the end and saved all of its value+address in a Set. I'm then iterated through LinkedList B and check if the value+address is present in the Set. If yes I know there is an intersection, and that the first time a match is found is the intersecting node. However, this solution didn't work. In the first test case, I see that node with value 1 has the same and has the same address in both lists and hence this must be the intersecting node. But the intersecting node is 8 and not 1. What's wrong here? A : 4-ListNode@20398b7c 1-ListNode@56235b8e 8-ListNode@3632be31 4-ListNode@5abca1e0 5-null B 5-ListNode@2286778 6-ListNode@4e9ba398 1-ListNode@56235b8e 8-ListNode@3632be31 4-ListNode@5abca1e0 5-null

[@yatharthvyas]

What if the two lists were: A: 10, 20, 30, 50, 60 B: 90, 20, 999, 50, 60 In this case, wouldn't the solution in video match and return 20 whereas the actual intersection happened at 50 after which all nodes were similar?

[@prakanshmishra9004]

No, this is because he is putting the equal condition on the nodes as a whole and not the values in the nodes. This is why, the nodes with 20 will be different nodes.

[@yatharthvyas]

@@prakanshmishra9004 Ohh, that's genius! Thanks

[@prakanshmishra9004]

@@yatharthvyas Actually, let me correct myself before anyone points it out. He is not comparing the nodes as a whole per se. He is comparing the pointers to the nodes, which will be different for the two nodes with 20 in your example. I am not totally sure how pointers actually work in Java (I usually work with C/C++ and Python) but that is what I think he is doing.

[@Paul-jx6tl]

great explanations !!!

[@davesnow7133]

this doesnt work if the last nodes are different. Two lists can have intersections WITHOUT having the same last element

[@sidhartheric4727]

Not possible for the last nodes to be different. A node can't have 2 different children. After the intersecting node, there can only be one path.

[@khanmuhammad3021]

What if they don't intersect the code is fail?

[@jatindigra4329]

Nailed it !! op solution !!!!!

[@akshitapatil2996]

What is the time complexity of this solution?

[@jagaya3662]

O(n), with n being the total length of both lists. Worst case: lists have different lengths and intersection is the final node -> both pointers go through each list once.

[@diegosuriaga3743]

@@jagaya3662 man thank u lol

[@moazzammatin9571]

The approach is showing a TLE in Leetcode.

[@prasadm3614]

Why can't we traverse from back and break the iteration where the elements of both lists are not equal ??

[@nishchalbhardwaj4835]

For that I think you might have to reverse the lists first, but not a bad idea

[@RacoonEvil]

I also thought of it, its with recursion though

[@nayanyadav6919]

You can't traverse from the back because the question states that these are 2 singly linked lists.

[@shivombhargava2166]

who the hell marked this question as easy in leetcode

[@cocoarecords]

Technical interview study guide for stacks and queue :{

[@mr_phamtastic]

awesome clean and concise

[@shyam2487]

thanks sir

[@gauravagrawal8381]

Good one

[@BharathCalgary]

This solution does not work in C#, as the object comparison in the while loop would result as false and the loop would continue untill they are null, so, in that case, i would use a hashset for the first list and then go through the second list, check the elements as I go through in the hashset and as soon as i hit the list element in the hashset, that is my intersection.

[@mangekostorm9211]

The point is to only use O(1) memory.

[@СыймыкРыскулов-я8ш]

You are genious

[@midhunpk3383]

When I tried this in python I got infinite loop running for cases with no intersection. I had to add a counter to monitor one full traversal!

[@priyamvashi2187]

wow. thanks

[@theSDE2]

As of now the problem has 6275 likes. I got stuck solving the question so came here.

[@Skkskk702]

thanks m8

[@murapovyerkhan2439]

awesome

[@dikshaaggarwal381]

You are the best 🔥

[@esranuryevgi6089]

If there is no intersection, is it going to infinite loop ? I dont get this point

[@jagaya3662]

No, they both reach the Null at the end of the lists at the same time, breaking out of the loop. List A has length a, list b has length b. If there is no intersection, after a+b steps, pointerA will be at the end of B, while pointerB will be at the end of A -> both pointers are at Null, therefore equal, therefore the while-loop isn't executed, ends and function returns Null.

[@victoriac7257]

Nick you look like you need more sleep

[@mujtabahussain7015]

in the example one, why can't the answer be, with '1' being the point of interseciton? 4------ 1-- 8-- 4-- 5 5 --6-