Python Program to Find Intersection and Union of Two Linked Lists

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

class LinkedList:
    def __init__(self):
        self.head = None

    def insert(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
        else:
            current = self.head
            while current.next:
                current = current.next
            current.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

    def find_intersection(self, other_list):
        intersection = LinkedList()
        current = self.head
        while current:
            if other_list.search(current.data):
                intersection.insert(current.data)
            current = current.next
        return intersection

    def search(self, data):
        current = self.head
        while current:
            if current.data == data:
                return True
            current = current.next
        return False

    def find_union(self, other_list):
        union = LinkedList()
        current = self.head

        while current:
            union.insert(current.data)
            current = current.next

        other_current = other_list.head
        while other_current:
            if not union.search(other_current.data):
                union.insert(other_current.data)
            other_current = other_current.next

        return union


list1 = LinkedList()
list1.insert(1)
list1.insert(2)
list1.insert(3)

list2 = LinkedList()
list2.insert(3)
list2.insert(4)
list2.insert(5)


print("Linked List 1:")
list1.display()

print("Linked List 2:")
list2.display()

intersection_result = list1.find_intersection(list2)
print("Intersection:")
intersection_result.display()

union_result = list1.find_union(list2)
print("Union:")
union_result.display()