Intersection of Two Linked Lists - Leetcode 160 - Python

0:00 - Read the problem
1:50 - Drawing Explanation
6:21 - Coding Explanation

leetcode 160

#amazon #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[neebuandsocanyou]

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

[ericnunez]

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

[ersinerdem]

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.

[rct]

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

[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.

[venkatasriharsha]

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!

[osmanmusse]

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

[zhakunigor]

The same logic can be used for Trees to find LCA

[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! <3

[ngneerin]

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

[davidmbugua]

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...

[daniell]

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?

[devolee]

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!

[filiszsz]

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!

[moade]

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

[complexnumber]

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

[aryanyadav]

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

[joshuaduffney]

An absolutely fantastic explanation, thank you!

[shan]

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!

[berylsam]

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