160. Intersection of Two Linked Lists - Day 6/30 Leetcode June Challenge

Larry solves and analyzes this Leetcode problem as both an interviewer and an interviewee. This is a live recording of a real engineer solving a problem live - no cuts or edits!

#leetcode #coding #programming

[lzr]

There is a cool trick you can do with this one, if you make two pointers one at start of A and one at start of B, then follow A whilst reversing the links as you go along, it will eventually go to c3 with the links from a1 to c3 now flipped. If you then do the same with the pointer at B and traverse again whilst reversing the links, because we reversed the links previously it will end up at A. Then for a final time, traverse with the first pointer (which would then be at C3) and reverse the links same as before. We are now left with the links all in the original position however with our two pointers in opposite places to where they started.

Now we can see that each node in the branches A, B and C have been visited two whilst the intersection has been visited 3 times. We can make an accumulator and use XOR on each address we visit in the traversal, this way we can count only the address which has been visited an odd number of times meaning that it will be the intersection. If the lists don't intersect then we have already reversed p twice so we just need to reverse q again and then return null for it to be in the original state.

I thought this was a different way of looking at things :D