Find Union and Intersection of two linked lists in Python

By Vineet Raj

In this tutorial, we learn to find the Union and Intersection of two linked lists in Python. The difference between the two sets is converted to a third set with elements common to both sets. The union between two sets is with all the elements from both sets in the third set.

Intersection

Union

The program creates two linked lists and finds its union and intersections.

Algorithm

• Let’s get started by creating a node with instance data(integer type) and a next pointer.
• After that Create a node LinkList with instance variable head(pointer holding address of head)).
• Then, Create a function prev_node, dup(duplicate), ins_end(insert at the end), display, and remove.
• The prev_node() function returns the previous node by taking a reference node as an argument.
• The ins_end function inserts a node at the end of the list.
• The display function will traverse the whole list and print the data(value) of each node.
• Remove function deletes it from the list by taking the node as an argument.
• The duplicate method returns a copy of the list.
• Define the function remove_dup that passes duplicate elements from the list as arguments.
• find_union function takes two linked lists as an argument and returns the union.
• So in the end, create a function find_intersec that two linked list as an argument and return the intersection of them.

Python Program

Creating a class Node:

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

Now create a class linked list:

class LinkList:
    def __init__(self):
        self.head = None
 
    def get_prev_node(self, ref_node):
        current = self.head
        while (current and current.next != ref_node):
            current = current.next
        return current
 
    def duplicate(self):
        copy = LinkList()
        current = self.head
        while current:
            node = Node(current.data)
            copy.insert_at_end(node)
            current = current.next
        return copy
 
    def insert_at_end(self, new_node):
        if self.head is None:
            self.head = new_node
        else:
            current = self.head
            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:
            self.head = self.head.next
        else:
            prev_node.next = node.next
 
    def display(self):
        current = self.head
        while current:
            print(current.data, end = ' ')
            current = current.next

For intersections, we need to remove some remaining elements from the linked list, so we need to create a function to do this.

def remove_duplicates(llist):
    current1 = llist.head
    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

So, till now we had formed the basis for our program, now we have to create a function union and intersection.

def find_union(llist1, llist2):
    if llist1.head is None:
        union = llist2.duplicate()
        remove_duplicates(union)
        return union
    if llist2.head is None:
        union = llist1.duplicate()
        remove_duplicates(union)
        return union
 
    union = llist1.duplicate()
    last_node = union.head
    while last_node.next is not None:
        last_node = last_node.next
    llist2_copy = llist2.duplicate()
    last_node.next = llist2_copy.head
    remove_duplicates(union)
 
    return union
 
 
def find_intersection(llist1, llist2):
    if (llist1.head is None or llist2.head is None):
        return LinkList()
 
    intersection = LinkList()
    current1 = llist1.head
    while current1:
        current2 = llist2.head
        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

We have created all the important classes and functions for our task, so now we have to call all those functions and classes from “main”.

a_llist1 = LinkList()
a_llist2 = LinkList()
data_list = input('Enter the elements of 1st linked list: ').split()
for data in data_list:
    node = Node(int(data))
    a_llist1.insert_at_end(node)
data_list = input('Enter the elements of 2nd 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 will be: ')
union.display()
print()
print('Their intersection will be: ')
intersection.display()
print()

Enter the elements of 1st linked list: 1 2 4 5 4 5 
Enter the elements of 2nd linked list: 6 5 1 3
Their union will be: 
1 2 4 5 6 3 
Their intersection will be: 
1 5

Add items to Python sets