Amazon Interview Question: Given the head pointers to tw... | Glassdoor

## Interview Question

Software Development Engineer Intern Interview Seattle, WA

# Given the head pointers to two linked lists of unknown

length, find the node of intersection if they do intersect.

1

If they do point to the same node at some point, that is the node of intersection. Otherwise, there is no intersection.

Interview Candidate on Jan 6, 2011
1

I don't understand the interview candidate's solution. I don't think I will work properly. If the last 3rd node of List A and last node of List B intersects, this algorithm will not find the answer.
My solutions: Suppose length of List A is m, length of List B is n,
If space cost is more of a concern, do a O(n^2) search because it will cost constant space to find the intersect. (nested for loop)
If time is more of a concern,
1. traverse through both list to figure out the length. Identify the smaller list(suppose it's list A). cost O(m+n).
2. traverse List A, build a binary search tree with the address of pointers of the list as payload O(m log(m)).
3. Traverse through list B and search the tree for each element in list B. if found, then it's the intersection.O(n log(m)).
the general complexity is O(m+n+(m+n)log(m)) = O((m+n)log(m)). If we don't suppose A is the shorter, then the time complexity will be O((m+n)log(min(m,n)))

William on Feb 13, 2011
5

pblm can be solved by making a circular linked list.
Start with head1 and traverse thru the list and modify the lastnode.nxtptr -&gt; head2
Now start with head2 and traverse. If you reach the head2 again then the list do intersect.

Vijay on Mar 10, 2011
0

Vijay has the best solution with linear time.

Anonymous on Mar 14, 2011
0

Vijay's solution works great for finding out whether they intersect, but the question asks for finding the node of intersection.

I think William's solution will work best for finding the node of intersection. The obvious one is an O(n^2) solution by traversing the first list with the nodes of the second list and doing a comparison.

PixelPerfect3 on Nov 1, 2011