How to get intersection point of 2 linked lists.
There are 2 lists A and B (we know the root nodes for both). We know that these 2 lists intersect at some point and after that it is common list (they merge into each other, or think of it as a Y list).
example: list A->1->2->3->4->5->6->end
Both the list intersect at node 4. This is what we need to find.
1. Find length of A
2. Find length of B
3. Find diff=length A-length B
4. Traverse larger list diff nodes (we know after this nodes will be equal for both lists).
5. Now traverse both list simultaneously and find out the common node (this is our required node).
More solutions here.
I like the solution 5 as well from solution lists. It is simply reversing the list A (6->5->4->-3->2->1).
So when we are traversing list 2 now we will get like 11->12->4->3->2->1->end (as the pointers are reversed). So we are actually calculating length(sum) of non-common part, And we already know length of 2 lists.
length A=A’+C(Common part)
and A’+B’=L (length of non-common part we found by traversing list B after reversing list A)
Three unknowns(A’, B’ and C) and three equations. Can’t get simpler than this.