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
[adinserter block=”2″]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
[adinserter block=”2″]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).