Intersection of two linked lists

Question

Anonymous · Accepted Answer

My solution:
Node getIntersect(Node headA,Node headB){
if(headA==null||headB==null)
return null;

Node first=headA,second=headB; 
while(first!=second){
 first=(first==null)?headB:first.next;
 second=(second==null)?headA:second.next;
}
return first;
}

Travis · Answer

O(n+m) 
Loop through first list, adding values to Hash Map or Set. 

Loop through second list and collect values that appear in list1's Hash Map or Set.

O(n+m2) - (quadratic)
If you cannot use a Set or Hash Map then 

Loop through the first list. Pause at every value to loop through the second list and check if the value exists.

Amazon

Amazon Interview Question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches