Challenge: Union and Intersection of Lists Using Hashing

Problem Statement

In this problem you have to implement two functions:

1. SinglyLinkedList<T> union(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2)
2. SinglyLinkedList<T> intersection(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2)

You have to implement these functions using Hashing. The first function will take two linked lists as input and return the union of the two lists. A Union of two sets can be expressed as, “Union of two sets A and B is a set which contains all the elements present in A or B”. Similarly, the second function will return the Intersection of two lists. The Intersection is commonly defined as, “A set which contains all the common elements present in A and B”.

Note: Your solution should also work if there is a duplicate in the lists, e.g.,

2->7->9->9->1

Hint: You can use the solution from the last challenge to help you out if needed.

Function Prototypes

public static <T> SinglyLinkedList<T> union(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2)
public static <T> SinglyLinkedList<T> intersection(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2)

Output

The union and intersection of two linked lists.

Note: The order of elements in the output list does not matter!

Sample Input

list1 = 15->22->8->null
list2 = 7->14->22->null

Sample Output

Union = 15->22->8->7->14->null
Intersection = 22->null