Challenge: Union & Intersection of Lists

Given two lists, find the Union & Intersection of their elements. Solve this exercise and see if your output matches the expected output.

Problem Statement

In this problem you have to implement two methods, i.e., SinglyLinkedList<T> union(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2) and SinglyLinkedList<T> intersection(SinglyLinkedList<T> list1, SinglyLinkedList<T> list2).

The first method 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 method will return the Intersection of two lists. The Intersection is commonly defined as, “A set which contains all the elements present in A and B”.

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

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

In the given SinglyLinkedList class below, you are provided with the method called removeDuplicatedWithHashing() this is another, much better approach for solving the previous challenge (But, we have discussed it in detail in Challenge: Remove Duplicate from a Linked List using Hashing). For now, you can use this function as a helper function to solve the current challenge. It can be used as:

list.removeDuplicatesWithHashing();

Method 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

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.