Intersection of Two Linked Lists - Leetcode 160 - Python

🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🥷 Discord: discord.gg/ddjKRXPqtk
🐦 Twitter: neetcode1
🐮 Support the channel: www.patreon.com/NEETcode
⭐ BLIND-75 PLAYLIST: kzbin.info/www/bejne/gX3PiXZ8fJqHpKM
💡 CODING SOLUTIONS: kzbin.info/aero/PLot-Xpze53leF0FeHz2X0aG3zd0mr1AW_
💡 DYNAMIC PROGRAMMING PLAYLIST: kzbin.info/www/bejne/bWTVZH6Nnqqpr80
🌲 TREE PLAYLIST: kzbin.info/www/bejne/hZ-2n2WOerZng7s
💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc
💡 BACKTRACKING PLAYLIST: kzbin.info/www/bejne/ppfMgpKGiJaabqc
💡 LINKED LIST PLAYLIST: kzbin.info/www/bejne/fWHCemCQe5WGaZo
💡 BINARY SEARCH PLAYLIST: kzbin.info/aero/PLot-Xpze53leNZQd0iINpD-MAhMOMzWvO
📚 STACK PLAYLIST: kzbin.info/aero/PLot-Xpze53lfxD6l5pAGvCD4nPvWKU8Qo
Python Code: github.com/neetcode-gh/leetcode/blob/main/160-Intersection-of-Two-Linked-Lists.py
Problem Link: leetcode.com/problems/intersection-of-two-linked-lists/
0:00 - Read the problem
1:50 - Drawing Explanation
6:21 - Coding Explanation
leetcode 160
This question was identified as an interview question from here: github.com/xizhengszhang/Leetcode_company_frequency
#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[@neebuandsocanyou7557]

Is it just me, or are these “easy” questions involving more and more tricks now.

[@samarpitgupta8000]

Right bro..most medium questions are standard ...but easy ones are tricky

[@bree9895]

yuh its better to see them first

[@alikhedr6638]

Its actually pretty easy if you use a hashmap he just wanted to show a smarter way to solve it with less memory

[@StfuSiriusly]

@@alikhedr6638 theres also a more intuitive way using O(1) he briefly went over it before his solution. Its the one i did when i first saw this problem. Just find the difference in the list lengths and move up a pointer by that difference. It requires a little more code but if you didnt know the 'trick' its an easy way to solve it using O(1) space

[@ericnunez223]

I got my first Amazon interview next week thanks for all the content !

[@dragonvslvr]

Good luck dude you got this!

[@illu_millu_tillu]

All the best buddy

[@rosewhip5332]

I hope you fail

[@AsifIqbalR]

Good luck, mate

[@joannelin5597]

Good luck ✨

[@ersinerdem7285]

Basically, make the two pointers pass the same distance in total, then they will certainly meet. The meeting is either on a node or at the end (null). The total distance passed will be m + n, as one pointer travels both the lists in no intersection case.

[@vishwasnegi5184]

thanks

[@rct4750]

Nice! This approach can also apply to this binary tree problem: 1650. Lowest Common Ancestor of a Binary Tree III

[@saarahasad3241]

Nice catch!

[@osmanmusse9432]

Hey neetcode great explanation, In example one in leetcode listA = [4,1,8,4,5], listB = [5,6,1,8,4,5] wouldn't there be an intersect around 1, I've been reading about some about address, but I could'nt understand

[@dominikilja]

I had an issue with that as well, but they mention why in the instructions. "1" is the value of two completely different nodes in memory. While "8" in both lists is referencing the same location in memory and that's why "8" is the intersection and not "1". Hope this is helpful!

[@thepinkcodon]

Thank you so much! I'm prepping for fte roles in data science/ml, and your videos have been super helpful for DS and algo part of the syllabus!

[@zhakunigor]

The same logic can be used for Trees to find LCA

[@venkatasriharsha4227]

Another simple approach is to just join one end of linkedlist with start of another linkedlist, then it's FLOYDS Algorithm(Cycle Detection Problem). 😁 Hope u can code it up!

[@not.a.casual]

yeah, but we have to retain their original structure, right?

[@crr004]

@@not.a.casual That's right. But even if you could use Floyd's algorithm I don't think you could return the node where they intersect, only detect if they do intersect or not.

[@CarlJohnson-iv7sn]

@@crr004 exactly. I was able to think of cycle detection as well but not sure how that'll be useful here. If it was a doubly linked list then ig but here we can't go back.

[@abbbhhi]

@@crr004 it is possible to find the intersection - 1. use Floyd's algorithm first to find whether the list have intersection or not 2. just move one of your pointer to the head, usually the slow pointer 3. Now, move both the slow and fast pointers one step at a time 4. the point at which they meet again is the start of the cycle or intersection of two list.

[@TheAcebyte]

I found a pretty neat solution, which beats more than 96 % on LeetCode, just wondered if it met the time and space complexity requirements: 1 - Find the smaller linked list by calculating the length of each. 2 - Reverse the smaller linked list and connect its head to the longer one. 3 - We now have a linked list cycle whose head is that intersection point, how do we find the head of a cycle? Tortoise and Hare. 4 - Undo any changes made to the smaller linked list to meet the "The linked lists have to retain their original structure AFTER the function returns" requirement.

[@daniell7998]

I don't understand why this isn't an infinite loop. Say the two lists don't intersect. Then, everytime l1 == nullptr, it will be reset to headB, and the same goes for l2. Thus, the condition of while ( l1 != l2 ) would forever continue the loop. How is this not the case?

[@friesarecurly]

Null will still result as it will be the first "node" to intersect. Imagine combining both LL's together, but add a null node at the very end LL A: 2 - 6 - 4 && LL B: 1 - 5 2 - 6 - 4 - 1 - 5 - null 1 - 5 - 2 - 6 - 4 - null

[@devolee8302]

Wow. Such a clear and concise explanation! I watched other ones but by far this is the best of all! Especially suggesting multiple ways this problem can be solved!

[@OrangeCanoe]

Is this like a kind of "Fast and Slow" pointer thing? I would have no idea how to intuit a solution like the optimal solution.

[@davidmbugua6994]

In the first example, both lists have 1 before 8 so I think we will get 1 as the result instead of 8 since we return the first one that we've seen in the visited list. I am so confused...

[@abdulkarimahmed6629]

You are right I was also thinking the same thing. That solution isnt right. This would work if we add the address of the node in the hashmap.

[@zactamzhermin1434]

I think the leetcode example was erroneous, good catch. The question was very confusing ngl

[@dominikilja]

I had an issue with that as well, but they mention why in the instructions. "1" is the value of two completely different nodes in memory. While "8" in both lists is referencing the same location in memory and that's why "8" is the intersection and not "1". Hope this is helpful!

[@usa5450]

​@@dominikilja yes it's helpful

[@AustinWeeks]

That solution is so clever, love it!

[@ngneerin]

Good to see you here. I thought after Google you'll stop posting leetcode

[@SHUBHAMKUMAR-ce8ix]

in the cpp code solution of this question on your website you have written l1 = (l1 != NULL) ? l1 = l1->next : headA; for it will be headB and in its next line it will be headA instead of headB

[@aryanyadav3926]

But if we have to iterate mp twice for both the lists, then isn't it better to calculate the lengths first.

[@jiwachhetri9262]

you have to iterate to find length. so with length method you will be iterating twice as well

[@mohammadwahiduzzamankhan4397]

I just love your video. Can you please share your experience how you prepare for your google inetrview? I have a an upcoming FAANG inetrview it will be a great help.

[@shan504]

Hey Neetcode, what software(s) do you use for these videos, in particular the drawings? I think they’re real neat. Your drawings are really clean!

[@nathamuni9435]

Zoomit

[@complexnumber1514]

connect c3 to b1, run floyd cycle detection, find the entering node to cycle, set c3->next = null return the entering node.

[@ghzich017]

Hello i'm sort of new to this kind of stff what does O(1) and O(m + n) mean exactly?

[@dadonutinator]

Its called time complexity and denotes how fast a program runs relative to some independent variable like how long lists a and b are giving you O(m + n) Theres also space complexity which is the similar but with how much memory u need. O(1) means u use the same amt of memory regardless of the lists. Super important concept so i suggest looking it up. :)

[@srishtisrivastava1535]

This is so awesome. I have no words.

[@Sportsman134]

when you say a pointer is not null (if l1), does that mean the nodes not null or the values not null

[@berylsam889]

Thank! YOU! it took me so long to understand, your video explanation helped so much!

[@moade5700]

You are doing us all a great service, many thanks Man !

[@just_code_yt]

when does it return no intersection since the loop is infinite. how does this work when there is no intersection.

[@joshuaduffney]

An absolutely fantastic explanation, thank you!

[@krishnavamsi9326]

But, how does it return no intersetcion? Is it not supposed to end infinitely? because at the last step both l1 and l2 will be again pointing to headB and headA right??? pls. help

[@just_code_yt]

same question have you found the answer to this?

[@krishnavamsi9326]

@@just_code_yt No bro, I just left it! If you got the answer, do tell me!

[@ngneerin]

Third Solution def getIntersectionNode(headA, headB): curA = headA curB = headB while curA != curB: curA = curA.next if curA else headB curB = curB.next if curB else headA return curA

[@filiszsz4163]

I thought about an interesting solution. Since in the description is it specified that all node values will be positive this will work. First, go all the way through listA and flip all the values to their negatives. Now go through listB, and the first node with a negative value you find, is the intersection, but don't return it yet, just save pointer to some variable. Now finally, go all the way through listA again and unflip all the values back to positive, since the task requires us to leave the lists untouched. Now you can return your saved pointer. I sent the solution and it is accepted, give it a try. The time complexity should be O(m+n), since we're going twice through one list and once through other, and the space complexity is O(1), since you only need the variable for the saved return value and some iterators. Hope this helps!

[@nitaikodkani]

definitely an interesting solution! thanks

[@reehji]

what's the best way to obtain the interviews after grinding leetcode ? I have a data engineering/backend background so not a standard SWE background. Thanks everyone!

[@rameshmanne4036]

what happens when there is no intersection? while loop will go to infinite right?

[@tomiczdarko]

Even when they don't have an intersection point, they still intersect at NULL and that exists the while loop. Then you return pointerA which is null and null means that there is no intersection.

[@fayezabusharkh3987]

I feel this should be medium to solve in O(1) space It's not intuitive unless you've seen it before

[@sharad_dutta]

Very well explained solution. Kudos.

[@NeetCode]

Thanks

[@pichu8115]

Is there really anyone can think of this solution without being taught?

[@AshutoshKumar-es8xy]

Probably after 2 months of thinking day and night about the problem

[@samarpitgupta8000]

Can anyone tell me that why 1 is not the answer instead 8 to this question in its first example given on leetcode?

[@tomicz9850]

It seems like the problem has changed

[@usa5450]

Because the node address is different, it doesn't matter what's the value. Hope you understood nigg*

[@ngneerin]

Second solution def getIntersectionNode(headA, headB): m = {} head = headA countA = 0 while head: countA += 1 head = head.next head = headB countB = 0 while head: countB += 1 head = head.next while countA > countB: headA = headA.next countA -= 1 while countB > countA: headB = headB.next countB -= 1 while headA: if headA == headB: return headA headA = headA.next headB = headB.next return None

[@ayah717]

thank you! :) appreciate the hard work and effort you've put into this

[@sayedabdo6266]

I am from Egypt and I want to get an internship at Google and now I studied data structures and now I study algorithms and solve problems. And I want to start studying the backend in the web(I'm thinking of studying PHP + laravel ), but I don't know what is the most thing that will provide my opportunity to get the internship. Can you suggest a technology in backend and a plan make me are ready to apply at the end of the year?

[@hugenerretho9151]

have u applied for software company in Egypt like "HyperLink"?

[@KV-gy2mr]

Usually at tech interviews for companies like Uber,Lyft , pins, do they ask you easy, medium or hard questions? And is the code supposed to pass all the unit tests or is it more like a Google docs interview that doesn't run through anything but needs to look logically sound?

[@Cruzylife]

meds/hard

[@ImMrRoboto]

What whiteboard app do you use?

[@blazekiller93]

Can I ask why you chose to use python? Just curious as I'm studying for interviews and leaning towards python even though I use Java at work

[@varunshrivastava2706]

Because Python is easy to understand and code.

[@Terracraft321]

Shorter

[@staffeng]

I think it's better to implement this problem without this trick. There's no way one can come up with a trick like this on the fly, and it's kind of hard to remember as well.

[@mattg9601]

Beautiful solution.

[@nithinchitra1570]

Really Really thank you sir

[@oliverli8802]

what if both lists have the same length but don't have an intersection? wouldn't the while loop never end?

[@hamoodhabibi7026]

since it's a singly linked list they will both go till they hit null (after the last node)

[@arfeenmalik8331]

I had this same question: No, the loop will eventually end. It only made sense when I worked out an example. Say you have two lists: [2,3,4, NULL] and [5,6,7, NULL]. Both lists will be traversed by the algorithm, and they will still arrive at a NULL at the same time. PointerA -> [2, 3, 4 -> NULL] PointerB ->[5, 6, 7 -> NULL]. Since they are both equal, they will not traverse each other and return null. When one list is longer than the other, they will still arrive at a NULL value, but only after they have traversed both lists. two lists: [1,2,3,4, NULL] and [5,6,7, NULL]. PointerA -> [1, 2, 3, 4 -> NULL -> 5, 6, 7 -> NULL]. PointerB ->[5, 6, 7 -> NULL -> 1, 2, 3, 4 -> NULL]. Take note, since they are different lengths, they arrive at NULL at the end! Hope this helps

[@bohanzhou2416]

Can you post a hashmap solution as well?

[@swapanjain892]

std::unordered_set visited; ListNode* tempA=headA; ListNode* tempB=headB; while(tempA!=nullptr) { visited.insert(tempA); tempA=tempA->next; } while(tempB!=nullptr) { if(visited.find(tempB)!=visited.end()) { return tempB; } tempB=tempB->next; } return nullptr;

[@14BIDISHA]

Thanks!

[@Redbugist]

is this the same principle with hasCycle?

[@Chambersu]

Lol, most medium questions are easier than this..., still thanks for the good explanation

[@bruce716]

Thanks a lot. Your video is super helpful!!

[@hoyinli7462]

great and simple solution!

[@neelnishant6946]

Great explanation!

[@kale-lb5pr]

node* intersectionY(node* head1, node* head2) { if (head1 == NULL || head2 == NULL) return NULL; node* temp = head1; map mpp; // Insert nodes of the first linked list into the map while (temp != NULL) { mpp[temp]=1; temp = temp->next; } // Traverse the second linked list and check for intersection temp = head2; while (temp != NULL) { if (mpp.find(temp) != mpp.end()) { return temp; } cout

[@mehershrishtinigam5449]

OH MY GOD i feel small brain rn fr fr, thank uuuu

[@EE12345]

So are people actually able to come up with algorithms like these with pure inference without a similar technique beforehand? Because I definitely can't.

[@MomSpaghetti]

lmao i envy these kind of people, like how could you come up with something like that with no prior experience

[@nikhilgoyal007]

Hi! I wrote l1 = l1.next if l1.next else headB but doing that gives my a Time Limit error. Any idea why that would be ?

[@oatmeal979]

If l1 is at the node right before null, then l1.next == null. So, "if l1.next" will always be false because it's basically "if null else headB". So you're stuck in an infinite loop

[@nikhilgoyal007]

thank you!

[@numberonep5404]

yay more neetcoding :3

[@geekydanish5990]

Frist solution suggested by you class Solution: def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: def get_list_size(head): start = head size = 0 while start: start = start.next size += 1 return size size_a = get_list_size(headA) size_b = get_list_size(headB) size_diff = abs(size_a-size_b) # increment the start by the size diff of the larger list start_a,start_b = headA,headB if(size_a > size_b): for i in range(size_diff): start_a = start_a.next elif(size_a < size_b): for i in range(size_diff): start_b = start_b.next while start_a and start_b: if start_a == start_b: return start_a start_a = start_a.next start_b = start_b.next else: return None

[@geekydanish5990]

I know there is a scope for refactor this

[@flatmapper]

It took me two times to watch before I get the idea 😂😂😂

[@yoyocswpg]

The solution to the follow-up is definitely not EASY

[@cc-to2jn]

Another great vid!

[@PoovizhiKannansupersonic]

But if the lists don't intersect, this solution has no exit, right?

[@austinchettiar6784]

they intersect at null i guess

[@d_mvp]

How do you even come up with these

[@romannikiforov5122]

I am pretty sure when they say O(m + n) they actually mean O(m + n), not O(2(m + n))

[@User-ri1jz]

how the hell do you not have over million subscribers?

[@harshavardhankotni7545]

What will it return when there is no intersection point?

[@SATISH17869]

Both the pointers intersect at the end of their lists i.e Null.

[@thedarkworld3913]

@@SATISH17869 if there is no intersection how it will return null because if l1 become null it will go to the else part headB same goes for l2 !! Can you please help me to understand

[@SATISH17869]

@@thedarkworld3913 yes when either of them reaches null it will trigger the else part. But eventually, there will be a moment when both l1 and l2 will reach null at the same time, which will mean that l1 == l2 i.e an intersection was found at Null. Hence it would return null. If I wasn't clear enough, feel free to ask your doubts.

[@ngneerin]

First Solution def getIntersectionNode(headA, headB): m = {} while headA: m[headA] = True headA = headA.next while headB: if headB in m: return headB headB = headB.next return None

[@karthikreddygaddam3104]

Bro from where did u learnt python basically

[@Michael-bt8fn]

Look at Elements of Programming interview in Python

[@aianaabdyrakhmanova5439]

brilliant

[@bchen1403]

I AM IN AWE.

[@shreyagd7747]

it is not accepting my answer

[@skolarii]

I don't understand how this works when the lists do not intersect

[@vinaydeep26]

the lists intersect at nulls then

[@thedarkworld3913]

@@vinaydeep26 what if they are of different length l1.next become null and l2.next become any value then it will goes to headB !!! Please help me to understand this

[@IlyaLeontyev]

Black magic

[@TheElementFive]

Super cringe problem, especially for an easy

[@Jack-ss4re]

Is that easy level? ffs 😂

[@parthshah1563]

Hii there! You are an amazing person, just curious what's your real name?

[@austinchettiar6784]

heisenberg