Interview. Find similar items 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 the algorithm and encode it in Java

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

For example: If linked list 1 has 1-> 2-> 3-> 4-> 4-> 5-> 6, and linked list 2 has 1-> 3-> 6-> 4-> 2-> 8

The resulting linked list is 1-> 2-> 3-> 4-> 6

thanks

Answer 1

What about:

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

This keeps order, as in list1 . Of course, someone may complain that this is fraud, if the questionnaire meant that you had to build the algorithm yourself, but if the only restriction was “code in Java”, then this is an acceptable solution (and, most likely, more efficient and corrected , free of charge than any lower-level solution manually).

Answer 2

Create a hash table.
Go through the first list of links, mark the entries when you visit them. NA) Go through the second list of links, mark the entries (another flag, etc.) when you visit them. O (M)

Move the hash table and find all records with one LL member. Create new LL members when you find the entries. HE)

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

Note. Edited answer for Saurabha.

Answer 3

get the first linked list and start with the first element, compare it with the first element of the second linked list, if they are the same, add a value for the result and go to the second element of the first list, otherwise go to the second element of the second list, do this until until the values ​​are the same or you reach the second and second.

Answer 4

Using a HashSet for constant time contains an operation.

Iterating through the first list and adding them to a HashSet --- O (n) (Note: adding to a HashSet is a constant time)

Go to the second list and if hashSet.contains then add them to the list of results.

At the end of the loop, return the list of results