Solution: Union and Intersection of Linked Lists — Hashing

Let's solve the Union and Intersection of Linked Lists — Hashing problem.

We'll cover the following

Statement

Given two linked lists as inputs containing integer values, implement the union and intersection functions for the linked lists. The order of elements in the output lists doesn’t matter.

Here’s how to implement the functions:

  • UnionThis combines elements from two sets, removing duplicates, to form a new set with all unique elements from both original sets.: This function will take two linked lists as input and return a new linked list containing all the unique elements.

  • IntersectionThis identifies and collects elements that are common to both sets, excluding all others, to create a set of shared elements.: This function will take two linked lists as input and return all the common elements between them as a new linked list.

Constraints:

Let n be the number of nodes in both linked lists:

  • 0≤0 \leq n ≤5×102\leq 5 \times 10^2

  • −5×103≤-5 \times 10^3 \leq node.data ≤5×103\leq 5 \times 10^3

Solution

We need to implement two operations:

  • Combine the two linked lists to perform a union of linked lists.

  • Take out common elements from the linked lists to perform intersection.

Union of linked lists

Initially, check if either list1 or list2 is empty and return the nonempty list as the result. Next, while list1 has elements, add the data of the current node to a set of unique values. Similarly, while list2 has elements, add the data of its current node to the set of unique values. Iterate over the elements in the set of unique values and insert each element at the head of the result list. Finally, return the result list as the union of list1 and list2.

Let’s look at the following illustrations to get a better understanding of the union operation:

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