CODEWITHSUNDEEP
javaalgorithm
SuperMan
SuperMan

Reputation: 3584

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

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

Upvotes: 4

Views: 1769

Answers (4)

Barry
Barry

Reputation: 1665

Use HashSet for constant time contains operation.

Iterate through the first List and add them to a HashSet --- O(n) (Note addding to HashSet is a constant time)

Iterate through second list and if hashSet.contains then add them to a result list.

At the end of the loop return the result list

Upvotes: 0

Jack
Jack

Reputation: 1438

Create a hash table.
Go through first link list, mark entries as you visit them. O(N) Go through second link list, mark entries(different flag etc) as you visit them. O(M)

Traverse hash table and find all the entries with both LL member. Create new LL members as you find entries. O(H)

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

Note: Edited answer for Saurabh.

Upvotes: 2

nafiseh
nafiseh

Reputation: 129

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

Upvotes: 1

Joonas Pulakka
Joonas Pulakka

Reputation: 36577

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).

Upvotes: 7

Related Questions