Intersection of Two Linked Lists | LeetCode 160 | Amazon Coding Interview Tutorial

Intersection of Two Linked Lists solution: LeetCode 160

AFFILIATE LINKS
If you're interested in learning algorithms, these are great resources.

💲 All coupons and discounts 💲

Intersection of Two Linked Lists | LeetCode 160 | Amazon Coding Interview
#intersectionoftwolinkedlists #leetcode #algorithms #terriblewhiteboard #codinginterview

Click the time stamp to jump to different parts of the video.
00:00 Title
00:07 Problem readout
01:21 Whiteboard solution
05:04 Coding solution
10:51 Result and outro

[TerribleWhiteboard]

If there are any videos you'd like me to make or if you have any ideas on how to optimize this solution, let me know!

[sneezygibz]

Time O(N + M) where n is listA and m is listB correct?
Space O(1)

[voltairinedecleyre]

thank you for the excellent explanation

[Play-Date-Care]

For anyone who is confused the "math law" on why it'll guaranteed that A will meet B:
For example: two lists here, list A: 4, 1, 8, 4, 3, and listB: 2, 6, 1, 8, 4, 3;
If you Traval A, finish, then start to Travel B from headB, you will get: 4, 1, 8, 4, 3, 2, 6, 1, 8, 4, 3. In the same time, start travel B, then start travel B, you will get:
2, 6, 1, 8, 4, 3, 4, 1, 8, 4, 3.
Now if you compare these two list:
Travel from A then start from headB: 4, 1, 8, 4, 3, 2, 6, 1, 8, 4, 3
Travel from B then start from headA: 2, 6, 1, 8, 4, 3, 4, 1, 8, 4, 3
As you can see, at any point, it guaranteed to meet!

[PavanKumar-mrtd]

what an awesome explanation really i loved your ways of explanation..

[hyrdeshgangwar]

Thanks man! Another clear and concise explanation!

[nawendusingh]

In case of no intersection why wont the pointers go in a infinite loop?

[yashrajbasan]

but what if a and b is identical and after that there is intersection. intersection of linked list here is nothing but abstraction. in simple terms we have to find sequence of characters in both link list and should be same. right?

[leongrin]

If there is no intersection, wouldn't this become an infinite loop?

[rampagex]

I don't understand why switching the pointers to the opposite heads guarantees this to work? Surely, there must be some mathematical explanation for this, would you care to help me figure it out? I say this because while your intuition may find this to be clear, my intuition may not be the same as yours, and thus we shouldn't rely on our intuition if we wish to communicate clearly with others. I really want to figure this out. Thank you.

[alexxiao]

Great video. Wish you can explain more how to find the solution by switching LinkedList while traveling til the end. There are some math behind this.

[AhmedHemaz]

I solved it like this
create
l1Length
l2Length
the first iteration will have each list length
after that for the bigger length will advance its pointer to be the same length as the other list
then traverse both lists at the same time whenever they point to the same reference would be the intersection node

and that it's the code for it




public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int firstListLength = 0;
int secondListLength = 0;
ListNode firstListPointer = headA;
ListNode secondListPointer = headB;
while(firstListPointer != null) {
firstListLength++;
firstListPointer = firstListPointer.next;
}
while(secondListPointer != null) {
secondListLength++;
secondListPointer = secondListPointer.next;
}

firstListPointer = headA;
secondListPointer = headB;
for(int i = 0; i < Math.abs(secondListLength - firstListLength) ; i ++) {
if(secondListLength > firstListLength) secondListPointer = secondListPointer.next;
if(secondListLength < firstListLength) firstListPointer = firstListPointer.next;
}
while(firstListPointer != null) {
if(firstListPointer == secondListPointer) return firstListPointer;
secondListPointer = secondListPointer.next;
firstListPointer = firstListPointer.next;
}
return null;
}
}

[HiteshKumar-mdyk]

Hi, I really loved your explanation. Could you please make videos on backtracking questions like subset, permutation, combination etc. Those are really hard to understand. Thanks in advance

[cofing_challenge_]

Why you stop posting please try to upload video again

[SR-wevl]

@Terrible Whiteboard Can somebody please tell me what is the intuition behind the solution!? How one would up with something like this in an interview?

[shyamjitiwari]

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

[puneetmidha]

How are you taking care in case of no intersection?

[adithirao]

Could you provide some logic behind how you can come up with this pointer advancing method? I understand it with the example given but don't know how to prove it would always work.

[thomasvaeth]

Shouldn't you check if pointer1 is headA or headB before setting it to headB? What happens if headA has 10x more nodes than headB before intersecting?

[siweizhu]

I believe the hard part is about prove of this method not implementation and you gave 0 explanation about correctness behind this method