Union and Intersection of two Linked List using Hashing

Last Updated : 15 Sep, 2023

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elements in output lists doesn’t matter.

Examples:

Input:
   List1: 10 -> 15 -> 4 -> 20
   List2: 8 -> 4 -> 2 -> 10
Output:
   Intersection List: 4 -> 10
   Union List: 2 -> 8 -> 20 -> 4 -> 15 -> 10
Explanation: In this two lists 4 and 10 nodes 
are common. The union lists contains 
all the nodes of both the lists.

Input:
   List1: 1 -> 2 -> 3 -> 4
   List2: 3 -> 4 -> 8 -> 10
Output:
   Intersection List: 3 -> 4
   Union List: 1 -> 2 -> 3 -> 4 -> 8 -> 10
Explanation: In this two lists 4 and 3 nodes 
are common. The union lists contains 
all the nodes of both the lists.

We have already discussed Method-1 and Method-2 of this question. In this post, its Method-3 (Using Hashing) is discussed with a Time Complexity of O(m+n) i.e. better than both methods discussed earlier.

Implementation:
1- Start traversing both the lists.
   a) Store the current element of both lists
      with its occurrence in the map.
2- For Union: Store all the elements of the map 
   in the resultant list.
3- For Intersection: Store all the elements only 
   with an occurrence of 2 as 2 denotes that 
   they are present in both the lists.

Below is the C++ implementation of the above steps.

CPP

// C++ program to find union and intersection of 
// two unsorted linked lists in O(m+n) time. 
#include <bits/stdc++.h> 
using namespace std; 
  
struct Node { 
int data; 
struct Node* next; 
}; 
  
void push(struct Node** head_ref, int new_data) 
{ 
/* allocate node */
struct Node* new_node = (struct Node*)malloc( 
 sizeof(struct Node)); 
  
/* put in the data */
new_node->data = new_data; 
  
/* link the old list of the new node */
new_node->next = (*head_ref); 
  
/* move the head to point to the new node */
(*head_ref) = new_node; 
} 
  
struct Node* getIntersection(Node *head1,Node *head2) 
{ 
   unordered_map<int, bool> m; 
struct Node* result = NULL; 
  
   Node *p=head1; 
   while(p!=NULL){ 
       m[p->data]=true; 
       p=p->next; 
   } 
   p=head2; 
   while(p!=NULL){ 
       if(m[p->data]==true){ 
           push(&result,p->data); 
       } 
       p=p->next; 
   } 
return result; 
} 
  
struct Node *getUnion(Node *head1,Node *head2){ 
   set<int> union_list; 
   Node *p=head1; 
   while(p!=NULL){ 
       union_list.insert(p->data); 
       p=p->next; 
   } 
   p=head2; 
   while(p!=NULL){ 
       union_list.insert(p->data); 
       p=p->next; 
   } 
   Node *result=NULL; 
   for(auto i:union_list){ 
       push(&result,i); 
   } 
   return result; 
} 
void printList(struct Node* node) 
{ 
while (node != NULL) { 
 printf("%d ", node->data); 
 node = node->next; 
} 
} 
  
void printUnionIntersection(Node* head1,Node* head2) 
{ 
Node* intersection_list = getIntersection(head1,head2); 
Node* union_list = getUnion(head1,head2); 
  
printf("\nIntersection list is \n"); 
printList(intersection_list); 
printf("\nUnion list is \n"); 
printList(union_list); 
} 
int main() 
{ 
struct Node* head1 = NULL; 
struct Node* head2 = NULL; 
//list1 
   push(&head1, 1); 
push(&head1, 2); 
push(&head1, 3); 
push(&head1, 3); 
push(&head1, 4); 
push(&head1, 5); 
  
//list 2 
push(&head2, 1); 
push(&head2, 5); 
push(&head2, 6); 
  
printf("First list is \n"); 
printList(head1); 
  
printf("\nSecond list is \n"); 
printList(head2); 
  
printUnionIntersection(head1, head2); 
  
return 0; 
}

Java

//Java program to find union and intersection of 
// two unsorted linked lists in O(m+n) time. 
  
import java.io.*; 
import java.util.*; 
  
class GFG { 
      
    static void printList(Node node) 
    { 
        while (node != null) { 
            System.out.print(node.data+" "); 
            node = node.next; 
        } 
    } 
      
    //Utility function to store the 
   //elements of both list 
    static void storeEle(Node head1, Node head2,Map<Integer, Integer> eleOcc) 
    { 
        Node ptr1 = head1; 
        Node ptr2 = head2; 
       
        // Traverse both lists 
        while (ptr1 != null || ptr2 != null) { 
            // store element in the map 
            if (ptr1 != null) { 
                if(eleOcc.get(ptr1.data)==null){ 
                    eleOcc.put(ptr1.data,1); 
                }else{ 
                    eleOcc.put(ptr1.data,eleOcc.get(ptr1.data)+1); 
                } 
                ptr1 = ptr1.next; 
            } 
       
            // store element in the map 
            if (ptr2 != null) { 
                if(eleOcc.get(ptr2.data)==null){ 
                    eleOcc.put(ptr2.data,1); 
                }else{ 
                    eleOcc.put(ptr2.data,eleOcc.get(ptr2.data)+1); 
                } 
                ptr2 = ptr2.next; 
            } 
        } 
    } 
      
    //Function to get the union of two 
   //linked lists head1 and head2 
    static Node getUnion(Map<Integer, Integer> eleOcc) 
    { 
        Node result = null; 
       
        // Push all the elements into 
        // the resultant list 
        for (int key:eleOcc.keySet()){ 
            Node node = new Node(key); 
            node.next=result; 
            result=node; 
        } 
       
        return result; 
    } 
      
    // Prints union and intersection of 
    // lists with head1 and head2. 
    static void printUnionIntersection(Node head1,Node head2) 
    { 
        // Store all the elements of 
        // both lists in the map 
        Map<Integer, Integer> eleOcc = new HashMap<>(); 
        storeEle(head1, head2, eleOcc); 
       
        Node intersection_list = getIntersection(eleOcc); 
        Node union_list = getUnion(eleOcc); 
       
        System.out.println("\nIntersection list is: "); 
        printList(intersection_list); 
       
        System.out.println("\nUnion list is: "); 
        printList(union_list); 
    } 
      
    //Function to get the intersection of 
   //two linked lists head1 and head2 
    static Node getIntersection(Map<Integer, Integer> eleOcc) 
    { 
        Node result = null; 
       
        // Push a node with an element 
        // having occurrence of 2 as that 
        // means the current element is 
        // present in both the lists 
        for (int key:eleOcc.keySet()){ 
            if(eleOcc.get(key)==2){ 
                Node node = new Node(key); 
                node.next=result; 
                result=node; 
            } 
        } 
       
        // return resultant list 
        return result; 
    } 
      
    //Driver program to test above function 
    public static void main (String[] args) { 
          
        /* Start with the empty list */
        LinkedList l1 = new LinkedList(); 
        LinkedList l2 = new LinkedList(); 
          
        /*create a linked list 11->10->15->4->20 */
        l1.push(1); 
        l1.push(2); 
        l1.push(3); 
        l1.push(4); 
        l1.push(5); 
        
        /*create a linked list 8->4->2->10 */
        l2.push(1); 
        l2.push(3); 
        l2.push(5); 
        l2.push(6); 
          
        System.out.print("First List: \n"); 
        printList(l1.head); 
        System.out.println("\nSecond List: "); 
        printList(l2.head); 
          
        printUnionIntersection(l1.head, l2.head); 
          
    } 
} 
  
//Link list node 
class Node{ 
    int data; 
    Node next; 
    Node(int d){ 
        this.data=d; 
    } 
} 
  
//Utility class to create a linked list 
class LinkedList{ 
      
    Node head; 
      
    //A utility function to insert a node at the 
   //beginning of a linked list 
    void push(int new_data){  
          
        //allocate node and put in the data 
        Node new_node = new Node(new_data); 
          
        //link the old list of the new node 
        new_node.next = head; 
          
        //move the head to point to the new node 
        head=new_node; 
    } 
      
} 
  
//This code is contributed by shruti456rawal

Python3

# Python code for finding union and intersection of linkedList 
  
  
class linkedList: 
    def __init__(self): 
        self.head = None
        self.tail = None
  
    def insert(self, data): 
        if self.head is None: 
            self.head = Node(data) 
            self.tail = self.head 
        else: 
            self.tail.next = Node(data) 
            self.tail = self.tail.next
  
  
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# return the head of new list containing the intersection of 2 linkedList 
  
  
def findIntersection(head1, head2): 
    # creating a map 
    hashmap = {} 
  
    # traversing on first list 
    while(head1 != None): 
        data = head1.data 
        if(data not in hashmap.keys()): 
            hashmap[data] = 1
        head1 = head1.next
  
    # making a new linkedList 
    ans = linkedList() 
    while(head2 != None): 
        data = head2.data 
        if(data in hashmap.keys()): 
            # adding data to new list 
            ans.insert(data) 
        head2 = head2.next
    return ans.head 
  
# return the head of new list containing the union of 2 linkedList 
  
  
def union(head1, head2): 
    # creating a map 
    hashmap = {} 
  
    # traversing on first list 
    while(head1 != None): 
        data = head1.data 
        if(data not in hashmap.keys()): 
            hashmap[data] = 1
        head1 = head1.next
  
    while(head2 != None): 
        data = head2.data 
        if(data not in hashmap.keys()): 
            hashmap[data] = 1
        head2 = head2.next
  
    # making a new linkedList 
    ans = linkedList() 
  
    # traverse on hashmap 
    for key, value in hashmap.items(): 
        ans.insert(key) 
  
    return ans.head 
  
  
def printList(head): 
    while head: 
        print(head.data, end=' ') 
        head = head.next
    print() 
  
  
if __name__ == '__main__': 
  
    # first list 
    ll1 = linkedList() 
    ll1.insert(1) 
    ll1.insert(2) 
    ll1.insert(3) 
    ll1.insert(4) 
    ll1.insert(5) 
  
    # second list 
    ll2 = linkedList() 
    ll2.insert(1) 
    ll2.insert(3) 
    ll2.insert(5) 
    ll2.insert(6) 
  
    print("First list is ") 
    printList(ll1.head) 
  
    print("Second list is ") 
    printList(ll2.head) 
  
    print("Intersection list is") 
    printList(findIntersection(ll1.head, ll2.head)) 
  
    print("Union list is ") 
    printList(union(ll1.head, ll2.head)) 
  
  
# This code is contributed by Arpit Jain 

C#

// C# program to find union and intersection of 
// two unsorted linked lists in O(m+n) time. 
using System; 
using System.Collections; 
using System.Collections.Generic; 
   
// linked list node 
public class Node{ 
    public int data; 
    public Node next; 
    public Node(int d){ 
        data = d; 
        next = null; 
    } 
} 
  
class LinkedList{ 
    public static void printList(Node node){ 
        while (node != null){ 
            Console.Write(node.data + " "); 
            node = node.next; 
        } 
        Console.WriteLine(""); 
    } 
   
    public static Node push(Node head_ref, int new_data){ 
       // allocate node and put in the data 
        Node new_node = new Node(new_data); 
   
        // link the old list of the new node 
        new_node.next = head_ref; 
   
        // move the head to point to the new node 
        head_ref = new_node; 
        return head_ref; 
    } 
   
    public static Node getIntersection(Node head1, Node head2){ 
        SortedDictionary<int, bool> m = new SortedDictionary<int, bool>(); 
        Node result = null; 
          
        Node p = head1; 
        while(p != null){ 
            m[p.data] = true; 
            p = p.next; 
        } 
        p = head2; 
        while(p != null){ 
            if(m.ContainsKey(p.data) && m[p.data] == true){ 
                result = push(result, p.data); 
            } 
            p = p.next; 
        } 
        return result; 
    } 
   
    public static Node getUnion(Node head1, Node head2){ 
        HashSet<int> union_list = new HashSet<int>(); 
        Node p = head1; 
        while(p != null){ 
            union_list.Add(p.data); 
            p = p.next; 
        } 
        p = head2; 
        while(p != null){ 
            union_list.Add(p.data); 
            p = p.next; 
        } 
          
        Node result = null; 
        foreach(int value in union_list) { 
            result = push(result, value); 
        } 
        return result; 
    } 
   
    public static void printUnionIntersection(Node head1, Node head2){ 
        Node intersection_list = getIntersection(head1, head2); 
        Node union_list = getUnion(head1, head2); 
          
        Console.WriteLine("Intersection list is : "); 
        printList(intersection_list); 
        Console.WriteLine("Union list is : "); 
        printList(union_list); 
    } 
      
    // driver code to test above functions 
    public static void Main(string []args){ 
        Node head1 = null; 
        Node head2 = null; 
          
        // list1 
        head1 = push(head1, 1); 
        head1 = push(head1, 2); 
        head1 = push(head1, 3); 
        head1 = push(head1, 3); 
        head1 = push(head1, 4); 
        head1 = push(head1, 5); 
          
        // list2 
        head2 = push(head2, 1); 
          head2 = push(head2, 3); 
        head2 = push(head2, 5); 
        head2 = push(head2, 6); 
          
        Console.WriteLine("First list is : "); 
        printList(head1); 
        Console.WriteLine("Second list is : "); 
        printList(head2); 
          
        printUnionIntersection(head1, head2); 
    } 
} 
// THIS CODE IS CONTRIBUTED BY KIRTI AGARWAL(KIRTIAGARWAL23121999)

Javascript

// JavaScript program to find union and intersection of 
// two unsorted linked lists in O(m+n) time. 
// structure of a node 
class Node{ 
    constructor(data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
function push(head_ref, new_data){ 
    // allocate node and put in data 
    let new_node = new Node(new_data); 
      
    // link the old list of the new node 
    new_node.next = head_ref; 
      
    // move the head to point to the new node 
    head_ref = new_node; 
    return head_ref; 
} 
  
function getIntersection(head1, head2){ 
    let m = new Map(); 
    let result = null; 
      
    let p = head1; 
    while(p != null){ 
        m.set(p.data, true); 
        p = p.next; 
    } 
    p = head2; 
    while(p != null){ 
        if(m.has(p.data) && m.get(p.data) == true){ 
            result = push(result, p.data); 
        } 
        p = p.next; 
    } 
    return result; 
} 
  
function getUnion(head1, head2){ 
    let union_list = new Set(); 
    let p = head1; 
    while(p != null){ 
        union_list.add(p.data); 
        p = p.next; 
    } 
    p = head2; 
    while(p != null){ 
        union_list.add(p.data); 
        p = p.next; 
    } 
    let result = null; 
    union_list.forEach(function(value){ 
        result = push(result, value); 
    }) 
    return result; 
} 
  
function printList(node){ 
    while(node != null){ 
        document.write(node.data + " "); 
        node = node.next; 
    } 
} 
  
function printUnionIntersection(head1, head2){ 
    let intersection_list = getIntersection(head1,head2); 
    let union_list = getUnion(head1,head2); 
      
    console.log("Intersection list is : "); 
    printList(intersection_list); 
    console.log("Union list is : "); 
    printList(union_list); 
} 
  
// driver code to test above function 
let head1 = null; 
let head2 = null; 
  
// list1 
head1 = push(head1, 1); 
head1 = push(head1, 2); 
head1 = push(head1, 3); 
head1 = push(head1, 3); 
head1 = push(head1, 4); 
head1 = push(head1, 5); 
  
// list2 
head2 = push(head2, 1); 
head2 = push(head2, 5); 
head2 = push(head2, 6); 
  
console.log("First list is : "); 
printList(head1); 
  
console.log("Second list is : "); 
printList(head2); 
  
printUnionIntersection(head1, head2); 
  
// THIS CODE IS CONTRIBUTED BY YASH AGARWAL(YASHAGARWAL2852002)

Output:

First list is 
5 4 3 2 1 
Second list is 
6 5 3 1 
Intersection list is 
3 5 1 
Union list is 
3 4 6 5 2 1

We can also handle the case of duplicates by maintaining separate Hash-Maps for both the lists. Complexity Analysis:

Time Complexity: O(m+n). Here ‘m’ and ‘n’ are number of elements present in first and second lists respectively. Reason: For Union: Traverse both the lists, store the elements in Hash-map and update the respective count. For Intersection: Check if count of an element in hash-map is ‘2’.
Auxiliary Space: O(m+n). Use of Hash-map data structure for storing values.

S

Sahil Chhabra

Improve

Previous Article

Find whether an array is subset of another array

Pair with given Sum (Two Sum)

Similar Reads

Union and Intersection of two Linked List using Merge Sort

Given two Linked Lists, create union and intersection lists that contain the union and intersection of the elements present in the given lists. The order of elements in output lists doesn’t matter. Examples: Input: List1: 10 -> 15 -> 4 -> 20 List2: 8 -> 4 -> 2 -> 10Output: Intersection List: 4 -> 10 Union List: 2 -> 8 ->

Union and Intersection of two Linked Lists

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. The order of elements in output lists doesn't matter.Example: Input: List1: 10->15->4->20 List2: 8->4->2->10Output: Intersection List: 4->10 Union List: 2->8->20->4->15->10 R

C Program For Union And Intersection Of Two Linked Lists

Write a C program for a given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. The order of elements in output lists doesn't matter.Example: Input:List1: 10->15->4->20List2: 8->4->2->10Output:Intersection List: 4->10Union List: 2->8->20-

C++ Program For Union And Intersection Of Two Linked Lists

Write a C++ program for a given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. The order of elements in output lists doesn't matter.Example: Input:List1: 10->15->4->20List2: 8->4->2->10Output:Intersection List: 4->10Union List: 2->8->20

Java Program For Union And Intersection Of Two Linked Lists

Write a java program for a given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. The order of elements in output lists doesn't matter.Example: Input:List1: 10->15->4->20List2: 8->4->2->10Output:Intersection List: 4->10Union List: 2->8->2

Union and Intersection of two Graphs

Given two graphs G1 and G2, the task is to find the union and intersection of the two given graphs, i.e. (G1 ∪ G2) and (G1 ∩ G2). Examples: Input: G1 = { ("e1", 1, 2), ("e2", 1, 3), ("e3", 3, 4), ("e4", 2, 4) }, G2 = = { ("e4", 2, 4), ("e5", 2, 5), ("e6", 4, 5) }Output:G1 union G2 ise1 1 2e2 1 3e3 3 4e4 2 4e5 2 5e6 4 5G1 intersection G2 ise4 2 4Exp

Find Union and Intersection of two unsorted arrays

Given two unsorted arrays that represent two sets (elements in every array are distinct), find the union and intersection of two arrays. Example: arr1[] = {7, 1, 5, 2, 3, 6} arr2[] = {3, 8, 6, 20, 7} Then your program should print Union as {1, 2, 3, 5, 6, 7, 8, 20} and Intersection as {3, 6, 7}. Note that the elements of union and intersection can

Union and Intersection of two sorted arrays

Given two sorted arrays, find their union and intersection. Example: Input: arr1[] = {1, 3, 4, 5, 7} arr2[] = {2, 3, 5, 6} Output: Union : {1, 2, 3, 4, 5, 6, 7} Intersection : {3, 5} Input: arr1[] = {2, 5, 6} arr2[] = {4, 6, 8, 10} Output: Union : {2, 4, 5, 6, 8, 10} Intersection : {6} Union of Two-Sorted Arrays using SetsThe idea of the approach i

Union By Rank and Path Compression in Union-Find Algorithm

In the previous post, we introduced union find algorithm and used it to detect cycles in a graph. We used the following union() and find() operations for subsets. C/C++ Code // Naive implementation of find int find(int parent[], int i) { if (parent[i] == -1) return i; return find(parent, parent[i]); } // Naive implementation of union() void Union(i

Union-Find Algorithm | (Union By Rank and Find by Optimized Path Compression)

Check whether a given graph contains a cycle or not. Example: Input: Output: Graph contains Cycle. Input: Output: Graph does not contain Cycle. Prerequisites: Disjoint Set (Or Union-Find), Union By Rank and Path CompressionWe have already discussed union-find to detect cycle. Here we discuss find by path compression, where it is slightly modified t

Article Tags :

Practice Tags :