# Python Program to Find Intersection and Union of Two Linked Lists

«
»

This is a Python program to find the union and intersection of two linked lists.

Problem Description

The program creates two linked lists and finds their union and intersection.

Problem Solution

1. Create a class Node with instance variables data and next.
3. The variable head points to the first element in the linked list.
4. Define methods get_prev_node, duplicate, insert_at_end, remove and display.
5. The method get_prev_node takes a reference node as argument and returns the previous node. It returns None when the reference node is the first node.
6. The method insert_at_end inserts a node at the last position of the list.
7. The method remove takes a node as argument and removes it from the list.
8. The method display traverses the list from the first node and prints the data of each node.
9. The method duplicate creates a copy of the list and returns it.
10. Define the function remove_duplicates which removes duplicate elements from the list passed as argument.
11. Define the function find_union which returns the union of the two linked lists passed to it.
12. Define the function find_intersection which returns the intersection of the two linked lists passed to it.
13. Create two instances of LinkedList, append data to them and find their union and intersection.

Program/Source Code

Here is the source code of a Python program to find the union and intersection of two linked lists. The program output is shown below.

```class Node:
def __init__(self, data):
self.data = data
self.next = None

def __init__(self):

def get_prev_node(self, ref_node):
while (current and current.next != ref_node):
current = current.next
return current

def duplicate(self):
while current:
node = Node(current.data)
copy.insert_at_end(node)
current = current.next
return copy

def insert_at_end(self, new_node):
else:
while current.next is not None:
current = current.next
current.next = new_node

def remove(self, node):
prev_node = self.get_prev_node(node)
if prev_node is None:
else:
prev_node.next = node.next

def display(self):
while current:
print(current.data, end = ' ')
current = current.next

def remove_duplicates(llist):
while current1:
current2 = current1.next
data = current1.data
while current2:
temp = current2
current2 = current2.next
if temp.data == data:
llist.remove(temp)
current1 = current1.next

def find_union(llist1, llist2):
union = llist2.duplicate()
remove_duplicates(union)
return union
union = llist1.duplicate()
remove_duplicates(union)
return union

union = llist1.duplicate()
while last_node.next is not None:
last_node = last_node.next
llist2_copy = llist2.duplicate()
remove_duplicates(union)

return union

def find_intersection(llist1, llist2):

while current1:
data = current1.data
while current2:
if current2.data == data:
node = Node(data)
intersection.insert_at_end(node)
break
current2 = current2.next
current1 = current1.next
remove_duplicates(intersection)

return intersection

data_list = input('Please enter the elements in the first linked list: ').split()
for data in data_list:
node = Node(int(data))
a_llist1.insert_at_end(node)
data_list = input('Please enter the elements in the second linked list: ').split()
for data in data_list:
node = Node(int(data))
a_llist2.insert_at_end(node)

union = find_union(a_llist1, a_llist2)
intersection = find_intersection(a_llist1, a_llist2)

print('Their union: ')
union.display()
print()
print('Their intersection: ')
intersection.display()
print()```
Program Explanation

1. Two instances of LinkedList are created.
2. The user is prompted to enter the data items for the two lists.
3. The functions find_union and find_intersection are called to find their union and intersection respectively.
4. These are then displayed.

Runtime Test Cases
```Case 1:
Please enter the elements in the first linked list: 1 2 3 4 5
Please enter the elements in the second linked list: 3 4 5 6 7 8
Their union:
1 2 3 4 5 6 7 8
Their intersection:
3 4 5

Case 2:
Their union:
7 8
Their intersection:

Case 3:
Please enter the elements in the first linked list: 8 4 2 1 10 3 4 7 8
Please enter the elements in the second linked list: 5 6 3 4 3 2 5 2 8
Their union:
8 4 2 1 10 3 7 5 6
Their intersection:
8 4 2 3```

Sanfoundry Global Education & Learning Series – Python Programs.

To practice all Python programs, here is complete set of 150+ Python Problems and Solutions.

Participate in Python Programming Certification Contest of the Month Now! 