Solution: Union and Intersection of Linked Lists

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

We'll cover the following

Statement

Given the heads of two linked lists, head1 and head2, as inputs. Implement the union and intersection functions for the linked lists. The order of elements in the output lists doesn’t matter.

Here’s how you will 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

First, we check if either of the input linked lists is NULL. If one of the linked lists is empty, we return the other linked list as it is because the union of an empty linked list with another is simply the non-empty linked list. Otherwise, we start with the first linked list, head1, and iterate over it until we reach its last node. This iteration uses a pointer, current, that goes through the linked list until no more nodes follow. Once the last node of head1 is reached, we link its next pointer to the head of the second linked list, head2. This action effectively merges the two linked lists into one.

Removing duplicates

However, this merged linked list may still contain duplicate elements. We need to eliminate duplicates to ensure the uniqueness of elements in the union operation. We do this by initializing an outer_node pointer to traverse the merged linked list. Within this outer loop, we initialize another pointer, inner_node, to compare the current node’s data with subsequent nodes in the linked list. We check each node’s data within this inner loop to identify and remove duplicates.

When a duplicate node is found, we update the next of the inner_node to point to the node after the subsequent node of the inner_node. This way, we can skip the duplicate node by removing its address from the linked list. We repeat this process until all nodes in both linked lists have been examined.

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 80+ hands-on prep courses.