Find Intersection and Union of Two Linked Lists

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).

Back to: Data Structure > Data Structure - Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *