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.
We'll cover the following
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 calledremoveDuplicatedWithHashing()
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.