Interview: Find similar elements from two linked lists and return the result as a linked list

Question

This question was asked in an interview for my friend. The interviewer asked to find algorithm and code it in Java

Question : Find similar elements from two linked lists and return the result as a linked list

Eg: If linkedlist1 has 1->2->3->4->4->5->6 and linkedlist2 has 1->3->6->4->2->8

Resulted linkedlist 1->2->3->4->6

Thanks

Answer 1

How about:

return new LinkedList(new LinkedHashSet(list1).retainAll(list2));

This preserves the order as in list1. Of course someone might complain about this being cheating, if the questioner meant that you should build the algorithm yourself, but if the only restriction was "code it in Java", then this is a valid solution (and quite likely more efficient and bug-free than anyone's hand-made lower-level solution).