Table of Contents

In this article, we will find the union and intersection of two linked lists. We will have a singly linked list, and therefore, each node will have data and a reference to the next node. Moreover, union and intersection are concepts of sets, and in a set, all items are distinct. Therefore, we also assume that the linked list does not have duplicates. Let’s take an example.

The union of two linked lists is a linked list that contains all the items that are in linked list one or linked list two (or both).

The intersection of two linked lists is a list that contains those items that are in both linked lists.

Now that we have defined the problem let’s go ahead and talk about its solutions.

**Find Intersection and Union of Two Linked Lists – Solution I**

**Union**

A simple and straightforward solution is to traverse the first linked list and add all its elements to the result list. Then, iterate over the second list, and for each node, check if there is a node with the same value in the result list (or the first list). If such a node exists, then ignore it. Otherwise, add a new node with the current node’s value to the result list.

**Intersection**

Similar to the union approach, iterate over the first linked list. Now here for each node, we check if there is a node with the same data in the second linked list. If this is the case, we insert a new node with the current node’s value to the resulting linked list.

**Implementation**

The implementation of this approach is given below:

# node for the linked list class Node: def __init__(self, value=None, next=None): self.value = value self.next = next # reference to the next node # implementation of linked list class LinkedList: def __init__(self): self.head = None self.length = 0 # total number of elements in the linked list # adds a node at the start of the linked list def insert(self, value): node = Node(value, self.head) # create a node self.head = node self.length = 1 # increment the length # traverse the complete list and print each node's value def displayList(ll): temp = ll while temp: print(temp.value, end="\t") temp = temp.next print("") # check if a node with the given value exists in the linked list def itemExists(ll, value): temp = ll # iterate through the list while temp: if temp.value == value: # element is found return True temp = temp.next return False def union(ll1, ll2): result = LinkedList() # create a new linked list # iterate over the first linked list and add its elements in the result list temp = ll1 while temp: result.insert(temp.value) temp = temp.next # iterate over the 2nd linked list and add those elements in the result list that are not in result already temp = ll2 while temp: if not itemExists(result.head, temp.value): result.insert(temp.value) temp = temp.next return result.head def intersection(ll1, ll2): result = LinkedList() # create a new linked list # iterate over the first linked list temp = ll1 while temp: if itemExists( ll2, temp.value ): # if the current node's value exists in the second linked list, then add it to the result list result.insert(temp.value) temp = temp.next return result.head # create linked list 1 ll1 = LinkedList() ll1.insert(2) ll1.insert(6) ll1.insert(4) ll1.insert(3) # create linked list 2 ll2 = LinkedList() ll2.insert(11) ll2.insert(3) ll2.insert(2) union_ll = union(ll1.head, ll2.head) intersection_ll = intersection(ll1.head, ll2.head) print("Linked list 1") displayList(ll1.head) print("Linked list 2") displayList(ll2.head) print("Union of linked list 1 and 2") displayList(union_ll) print("Intersection of linked list 1 and 2") displayList(intersection_ll)

**Output**

Linked list 1 3 4 6 2 Linked list 2 2 3 11 Union of linked list 1 and 2 11 2 6 4 3 Intersection of linked list 1 and 2 2 3

This approach is simple but is not efficient. We get a time complexity of `O(m*n)`

in both cases. Here, `m`

and `n`

are the lengths of the first and second linked lists, respectively.

We can find a solution that is more efficient than this approach. Let’s discuss it.

**Find Intersection and Union of Two Linked Lists – Solution II**

The idea behind this method is to use hash tables to keep track of the items visited instead of checking every time whether that item exists in the other list or not.

**Union**

First, we iterate over the linked list one and add its elements in the result list just like we did in the above solution. However, we also store the current node’s value as a key in a hash table. Then, we iterate over the second list. For each node’s value, we check if it is in the hash table. If it is, we don’t add it to the result list. Otherwise, we do.

**Intersection**

We traverse the first linked list and add its elements as keys in the hash table. Then, we iterate over the second linked list and check if the current node’s value is in the hash table. If it is, we insert it in the result list.

**Implementation**

# traverse the complete list and print each node's value def displayList(ll): temp = ll while temp: print(temp.value, end="\t") temp = temp.next print("") def union(ll1, ll2): dictt = {} result = LinkedList() # iterate over the first linked list and add its elements in the result list and in the dictionary/hash table temp = ll1 while temp: result.insert(temp.value) dictt[temp.value] = 1 temp = temp.next # iterate over the second linked list and add those elements in the result list that are not in the dictionary/hash table temp = ll2 while temp: if ( dictt.get(temp.value, None) == None ): # this method returns None if there is no key with temp.value. Otherwise, returns its value result.insert(temp.value) temp = temp.next return result.head def intersection(ll1, ll2): dictt = {} result = LinkedList() # iterate over the first linked list and add its elements in the dictionary/hash table temp = ll1 while temp: dictt[temp.value] = 1 temp = temp.next # iterate over the second linked list and add those elements in the result list that are in the dictionary/hash table temp = ll2 while temp: if dictt.get( temp.value, None ): # this method returns None if there is no key with temp.value. Otherwise, returns its value result.insert(temp.value) temp = temp.next return result.head # create linked list 1 ll1 = LinkedList() ll1.insert(2) ll1.insert(6) ll1.insert(4) ll1.insert(3) # create linked list 2 ll2 = LinkedList() ll2.insert(11) ll2.insert(3) ll2.insert(2) union_ll = union(ll1.head, ll2.head) intersection_ll = intersection(ll1.head, ll2.head) print("Linked list 1") displayList(ll1.head) print("Linked list 2") displayList(ll2.head) print("Union of linked list 1 and 2") displayList(union_ll) print("Intersection of linked list 1 and 2") displayList(intersection_ll)

**Output**

Linked list 1 3 4 6 2 Linked list 2 2 3 11 Union of linked list 1 and 2 11 2 6 4 3 Intersection of linked list 1 and 2 3 2

The time complexity of this approach is `O(m+n)`

.

Blog Hero