Find similar elements from two Linked Lists and return the result as a Linked List

Consider:

list1: 1->2->3->4->4->5->6
list2: 1->3->6->4->2->8

Result:

list3: 1->2->3->4->6

1. Create a hash table or set
2. Go through list1, mark entries as you visit them. O(N)
3. Go through list2, mark entries (with different flag) as you visit them. O(M)
4. Traverse hash table and find all the entries with both flags. Create list3 as you find entries. O(H)

Total Complexity: O(N)+ O(M) + O(Max(N,H,M)) => O(N)