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->10
Output:
Intersection List: 4->10
Union List: 2->8->20->4->15->10
Method 1 (Simple):
The following are simple algorithms to get union and intersection lists respectively.
Intersection (list1, list2)
Initialize the result list as NULL. Traverse list1 and look for every element in list2, if the element is present in list2, then add the element to the result.
Union (list1, list2):
Initialize a new list ans and store first and second list data to set to remove duplicate data
and then store it into our new list ans and return its head.
C++
// C++ program to find union// and intersection of two unsorted// linked lists#include "bits/stdc++.h"using namespace std;/* Linked list node */struct Node { int data; struct Node* next; Node(int x) { data = x; next = NULL; }};/* A utility function to insert anode at the beginning ofa linked list*/void push(struct Node** head_ref, int new_data);/* A utility function to check ifgiven data is present in a list */bool isPresent(struct Node* head, int data);/* Function to get union of twolinked lists head1 and head2 */struct Node* getUnion(struct Node* head1, struct Node* head2){ struct Node* ans = new Node(-1); struct Node* head = ans; set<int> st; while (head1 != NULL) { st.insert(head1->data); head1 = head1->next; } while (head2 != NULL) { st.insert(head2->data); head2 = head2->next; } for (auto it : st) { struct Node* t = new Node(it); ans->next = t; ans = ans->next; } head = head->next; return head;}/* Function to get intersection oftwo linked lists head1 and head2 */struct Node* getIntersection(struct Node* head1, struct Node* head2){ struct Node* result = NULL; struct Node* t1 = head1; // Traverse list1 and search each element of it in // list2. If the element is present in list 2, then // insert the element to result while (t1 != NULL) { if (isPresent(head2, t1->data)) push(&result, t1->data); t1 = t1->next; } return result;}/* A utility function to insert anode at the beginning of a linked list*/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;}/* A utility function to print a linked list*/void printList(struct Node* node){ while (node != NULL) { cout << " " << node->data; node = node->next; }}bool isPresent(struct Node* head, int data){ struct Node* t = head; while (t != NULL) { if (t->data == data) return 1; t = t->next; } return 0;}/* Driver program to test above function*/int main(){ /* Start with the empty list */ struct Node* head1 = NULL; struct Node* head2 = NULL; struct Node* intersecn = NULL; struct Node* unin = NULL; /*create a linked lists 10->15->5->20 */ push(&head1, 20); push(&head1, 4); push(&head1, 15); push(&head1, 10); /*create a linked lists 8->4->2->10 */ push(&head2, 10); push(&head2, 2); push(&head2, 4); push(&head2, 8); intersecn = getIntersection(head1, head2); unin = getUnion(head1, head2); cout << "\n First list is " << endl; printList(head1); cout << "\n Second list is " << endl; printList(head2); cout << "\n Intersection list is " << endl; printList(intersecn); cout << "\n Union list is " << endl; printList(unin); return 0;}// This code is contributed by zishanahmad786 |
C
// C program to find union// and intersection of two unsorted// linked lists#include <stdbool.h>#include <stdio.h>#include <stdlib.h>/* Linked list node */struct Node { int data; struct Node* next;};/* A utility function to insert a node at the beginning ofa linked list*/void push(struct Node** head_ref, int new_data);/* A utility function to check if given data is present in a list */bool isPresent(struct Node* head, int data);/* Function to get union of two linked lists head1 and head2 */struct Node* getUnion(struct Node* head1, struct Node* head2){ struct Node* result = NULL; struct Node *t1 = head1, *t2 = head2; // Insert all elements of // list1 to the result list while (t1 != NULL) { push(&result, t1->data); t1 = t1->next; } // Insert those elements of list2 // which are not present in result list while (t2 != NULL) { if (!isPresent(result, t2->data)) push(&result, t2->data); t2 = t2->next; } return result;}/* Function to get intersection of two linked lists head1 and head2 */struct Node* getIntersection(struct Node* head1, struct Node* head2){ struct Node* result = NULL; struct Node* t1 = head1; // Traverse list1 and search each element of it in // list2. If the element is present in list 2, then // insert the element to result while (t1 != NULL) { if (isPresent(head2, t1->data)) push(&result, t1->data); t1 = t1->next; } return result;}/* A utility function to insert a node at the beginning of a linked list*/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;}/* A utility function to print a linked list*/void printList(struct Node* node){ while (node != NULL) { printf("%d ", node->data); node = node->next; }}/* A utility function that returns true if data is present in linked list else return false */bool isPresent(struct Node* head, int data){ struct Node* t = head; while (t != NULL) { if (t->data == data) return 1; t = t->next; } return 0;}/* Driver program to test above function*/int main(){ /* Start with the empty list */ struct Node* head1 = NULL; struct Node* head2 = NULL; struct Node* intersecn = NULL; struct Node* unin = NULL; /*create a linked lists 10->15->5->20 */ push(&head1, 20); push(&head1, 4); push(&head1, 15); push(&head1, 10); /*create a linked lists 8->4->2->10 */ push(&head2, 10); push(&head2, 2); push(&head2, 4); push(&head2, 8); intersecn = getIntersection(head1, head2); unin = getUnion(head1, head2); printf("\n First list is \n"); printList(head1); printf("\n Second list is \n"); printList(head2); printf("\n Intersection list is \n"); printList(intersecn); printf("\n Union list is \n"); printList(unin); return 0;} |
Java
// Java program to find union and// intersection of two unsorted// linked listsclass LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to get Union of 2 Linked Lists */ void getUnion(Node head1, Node head2) { Node t1 = head1, t2 = head2; // insert all elements of list1 in the result while (t1 != null) { push(t1.data); t1 = t1.next; } // insert those elements of list2 // that are not present while (t2 != null) { if (!isPresent(head, t2.data)) push(t2.data); t2 = t2.next; } } void getIntersection(Node head1, Node head2) { Node result = null; Node t1 = head1; // Traverse list1 and search each // element of it in list2. // If the element is present in // list 2, then insert the // element to result while (t1 != null) { if (isPresent(head2, t1.data)) push(t1.data); t1 = t1.next; } } /* Utility function to print list */ void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /* Inserts a node at start of linked list */ void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* A utility function that returns true if data is present in linked list else return false */ boolean isPresent(Node head, int data) { Node t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist1 = new LinkedList(); LinkedList llist2 = new LinkedList(); LinkedList unin = new LinkedList(); LinkedList intersecn = new LinkedList(); /*create a linked lists 10->15->4->20 */ llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); /*create a linked lists 8->4->2->10 */ llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersecn.getIntersection(llist1.head, llist2.head); unin.getUnion(llist1.head, llist2.head); System.out.println("First List is"); llist1.printList(); System.out.println("Second List is"); llist2.printList(); System.out.println("Intersection List is"); intersecn.printList(); System.out.println("Union List is"); unin.printList(); }} /* This code is contributed by Rajat Mishra */ |
Python3
# Python program to find union and# intersection of two unsorted# linked lists# Linked list Nodeclass Node: def __init__(self, data): self.data = data self.next = Noneclass LinkedList: def __init__(self): self.head = None # Function to get Union of 2 Linked Lists def getUnion(self, head1, head2): t1 = head1 t2 = head2 # insert all elements of list1 in the result while t1 is not None: self.push(t1.data) t1 = t1.next # insert those elements of list2 # that are not present while t2 is not None: if not self.isPresent(self.head, t2.data): self.push(t2.data) t2 = t2.next def getIntersection(self, head1, head2): t1 = head1 # Traverse list1 and search each # element of it in list2. # If the element is present in # list 2, then insert the # element to result while t1 is not None: if self.isPresent(head2, t1.data): self.push(t1.data) t1 = t1.next # Utility function to print list def printList(self): temp = self.head while temp is not None: print(temp.data, end=" ") temp = temp.next print("") # Inserts a node at start of linked list def push(self, new_data): new_node = Node(new_data) # Make next of new Node as head new_node.next = self.head # Move the head to point to new Node self.head = new_node # A utility function that returns true # if data is present in linked list # else return false def isPresent(self, head, data): t = head while t is not None: if t.data == data: return True t = t.next return False# Driver program to test above functionsif __name__ == '__main__': llist1 = LinkedList() llist2 = LinkedList() unin = LinkedList() intersecn = LinkedList() # create a linked lists 10->15->4->20 llist1.push(20) llist1.push(4) llist1.push(15) llist1.push(10) # create a linked lists 8->4->2->10 llist2.push(10) llist2.push(2) llist2.push(4) llist2.push(8) intersecn.getIntersection(llist1.head, llist2.head) unin.getUnion(llist1.head, llist2.head) print("First List is") llist1.printList() print("Second List is") llist2.printList() print("Intersection List is ") intersecn.printList() print("Union List is ") unin.printList() # This code is contributed by lokesh. |
C#
// C# program to find union and// intersection of two unsorted// linked listsusing System;class LinkedList { public Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* Function to get Union of 2 Linked Lists */ void getUnion(Node head1, Node head2) { Node t1 = head1, t2 = head2; // insert all elements of list1 in the result while (t1 != null) { push(t1.data); t1 = t1.next; } // insert those elements of list2 // that are not present while (t2 != null) { if (!isPresent(head, t2.data)) push(t2.data); t2 = t2.next; } } void getIntersection(Node head1, Node head2) { Node t1 = head1; // Traverse list1 and search each // element of it in list2. // If the element is present in // list 2, then insert the // element to result while (t1 != null) { if (isPresent(head2, t1.data)) push(t1.data); t1 = t1.next; } } /* Utility function to print list */ void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } /* Inserts a node at start of linked list */ void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } /* A utility function that returns true if data is present in linked list else return false */ bool isPresent(Node head, int data) { Node t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } /* Driver code*/ public static void Main(string[] args) { LinkedList llist1 = new LinkedList(); LinkedList llist2 = new LinkedList(); LinkedList unin = new LinkedList(); LinkedList intersecn = new LinkedList(); /*create a linked lists 10->15->5->20 */ llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); /*create a linked lists 8->4->2->10 */ llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersecn.getIntersection(llist1.head, llist2.head); unin.getUnion(llist1.head, llist2.head); Console.WriteLine("First List is"); llist1.printList(); Console.WriteLine("Second List is"); llist2.printList(); Console.WriteLine("Intersection List is"); intersecn.printList(); Console.WriteLine("Union List is"); unin.printList(); }}// This code is contributed by rutvik_56. |
Javascript
<script> //Javascript program to find union and // intersection of two unsorted // linked lists /* Linked list Node*/ class Node { constructor(d) { this.data = d; this.next = null; } } class LinkedList{ constructor(){ this.head=null; } /* Inserts a node at start of linked list */ push(new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ var new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = this.head; /* 4. Move the head to point to new Node */ this.head = new_node; } /* A utility function that returns true if data is present in linked list else return false */ isPresent(head, data) { var t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } /* Function to get Union of 2 Linked Lists */ getUnion(head1, head2) { var t1 = head1, t2 = head2; // insert all elements of list1 in the result while (t1 != null) { this.push(t1.data); t1 = t1.next; } // insert those elements of list2 // that are not present while (t2 != null) { if (!this.isPresent(this.head, t2.data)) this.push(t2.data); t2 = t2.next; } } getIntersection(head1, head2) { var result = null; var t1 = head1; // Traverse list1 and search each // element of it in list2. // If the element is present in // list 2, then insert the // element to result while (t1 != null) { if (this.isPresent(head2, t1.data)) this.push(t1.data); t1 = t1.next; } } /* Utility function to print list */ printList() { var temp = this.head; while (temp != null) { document.write(temp.data + " "); temp = temp.next; } } } const llist1 = new LinkedList(); const llist2 = new LinkedList(); const unin = new LinkedList(); const intersecn = new LinkedList(); /*create a linked lists 10->15->4->20 */ llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); /*create a linked lists 8->4->2->10 */ llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersecn.getIntersection(llist1.head, llist2.head); unin.getUnion(llist1.head, llist2.head); document.write("First List is "); llist1.printList(); document.write("Second List is "); llist2.printList(); document.write("Intersection List is "); intersecn.printList(); document.write("Union List is "); unin.printList(); //This code is contributed by shruti456rawal</script> |
Output
First list is 10 15 4 20 Second list is 8 4 2 10 Intersection list is 4 10 Union list is 2 8 20 4 15 10
Complexity Analysis:
- Time Complexity: O(m*n).
Here ‘m’ and ‘n’ are number of elements present in the first and second lists respectively.
For union: For every element in list-2 we check if that element is already present in the resultant list made using list-1.
For intersection: For every element in list-1 we check if that element is also present in list-2. - Auxiliary Space: O(1).
No use of any data structure for storing values.
Method 2 (Use Merge Sort):
In this method, algorithms for Union and Intersection are very similar. First, we sort the given lists, then we traverse the sorted lists to get union and intersection.
The following are the steps to be followed to get union and intersection lists.
- Sort the first Linked List using merge sort. This step takes O(mLogm) time. Refer this post for details of this step.
- Sort the second Linked List using merge sort. This step takes O(nLogn) time. Refer this post for details of this step.
- Linearly scan both sorted lists to get the union and intersection. This step takes O(m + n) time. This step can be implemented using the same algorithm as sorted arrays algorithm discussed here.
The time complexity of this method is O(mLogm + nLogn) which is better than method 1’s time complexity.
C++
#include <iostream>using namespace std;class Node {public: int data; Node* next; Node(int data) { this->data = data; this->next = NULL; }};// function to print linked listvoid printLinkedList(Node* head) { Node* temp = head; while (temp != NULL) { cout << temp->data << "-->"; temp = temp->next; } cout << "None";}// function to get union of two linked listsNode* getUnion(Node* ll1, Node* ll2) { Node* tail = NULL; Node* head = NULL; while (ll1 != NULL || ll2 != NULL) { if (ll1 == NULL) { if (tail == NULL) { tail = new Node(ll2->data); head = tail; } else { tail->next = new Node(ll2->data); tail = tail->next; } ll2 = ll2->next; } else if (ll2 == NULL) { if (tail == NULL) { tail = new Node(ll1->data); head = tail; } else { tail->next = new Node(ll1->data); tail = tail->next; } ll1 = ll1->next; } else { if (ll1->data < ll2->data) { if (tail == NULL) { tail = new Node(ll1->data); head = tail; } else { tail->next = new Node(ll1->data); tail = tail->next; } ll1 = ll1->next; } else if (ll1->data > ll2->data) { if (tail == NULL) { tail = new Node(ll2->data); head = tail; } else { tail->next = new Node(ll2->data); tail = tail->next; } ll2 = ll2->next; } else { if (tail == NULL) { tail = new Node(ll1->data); head = tail; } else { tail->next = new Node(ll1->data); tail = tail->next; } ll1 = ll1->next; ll2 = ll2->next; } } } return head;}// main function to test the codeint main() { // create first linked list Node* head1 = new Node(10); head1->next = new Node(20); head1->next->next = new Node(30); head1->next->next->next = new Node(40); head1->next->next->next->next = new Node(50); head1->next->next->next->next->next = new Node(60); head1->next->next->next->next->next->next = new Node(70); // create second linked list Node* head2 = new Node(10); head2->next = new Node(30); head2->next->next = new Node(50); head2->next->next->next = new Node(80); head2->next->next->next->next = new Node(90); Node* head = getUnion(head1, head2); printLinkedList(head); cout << endl; return 0;}// This code is contributed by Gaurav |
Java
class Node { int data; Node next; Node(int data) { this.data = data; this.next = null; }}public class LinkedListUnion { static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // function to print linked list public static void printLinkedList(Node head) { Node temp = head; while (temp != null) { System.out.print(temp.data + "-->"); temp = temp.next; } System.out.print("None");} // function to get union of two linked lists static Node getUnion(Node ll1, Node ll2) { Node tail = null; Node head = null; while (ll1 != null || ll2 != null) { if (ll1 == null) { if (tail == null) { tail = new Node(ll2.data); head = tail; } else { tail.next = new Node(ll2.data); tail = tail.next; } ll2 = ll2.next; } else if (ll2 == null) { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; } else { if (ll1.data < ll2.data) { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; } else if (ll1.data > ll2.data) { if (tail == null) { tail = new Node(ll2.data); head = tail; } else { tail.next = new Node(ll2.data); tail = tail.next; } ll2 = ll2.next; } else { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; ll2 = ll2.next; } } } return head; } // main function to test the code public static void main(String[] args) { // create first linked list Node head1 = new Node(10); head1.next = new Node(20); head1.next.next = new Node(30); head1.next.next.next = new Node(40); head1.next.next.next.next = new Node(50); head1.next.next.next.next.next = new Node(60); head1.next.next.next.next.next.next = new Node(70); // create second linked list Node head2 = new Node(10); head2.next = new Node(30); head2.next.next = new Node(50); head2.next.next.next = new Node(80); head2.next.next.next.next = new Node(90); Node head = getUnion(head1, head2); printLinkedList(head); System.out.println(); }}// This code is contributed by Vikram_Shirsat |
Python3
def merge(ll1,ll2): if ll1 is None: return ll2 if ll2 is None: return ll1 if ll1.data==ll2.data: head=ll1 tail=ll1 ll1=ll1.next ll2=ll2.next elif ll1.data>ll2.data: head=ll2 tail=ll2 ll2=ll2.next else: head=ll1 tail=ll1 ll1=ll1.next while ll1 is not None and ll2 is not None: if ll1.data==ll2.data: tail.next=ll1 tail=ll1 ll1=ll1.next ll2=ll2.next elif ll1.data>ll2.data: tail.next=ll2 tail=ll2 ll2=ll2.next else: tail.next=ll1 tail=ll1 ll1=ll1.next if ll1 is not None: tail.next=ll1 if ll2 is not None: tail.next=ll2 return headdef mid_point_2(head): if head is None: return None slow=head fast=head while fast.next is not None and fast.next.next is not None: slow=slow.next fast=fast.next.next return slow def merge_sort(head): if head is None or head.next is None: return head mid=mid_point_2(head) head2=merge_sort(mid.next) mid.next=None head1=merge_sort(head) final_head=merge(head1,head2) return final_head def union(head1,head2): # code here # return head of resultant linkedlist head1=merge_sort(head1) head2=merge_sort(head2) return merge(head1,head2) # Driver Code Starts#Initial Template for Python 3class Node: def __init__(self,data): self.data=data self.next=None def print_ll(head): while head is not None: print(head.data,end='-->') head=head.next print('None') def take_input(l): if len(l)==0 or l[0]==-1: return head,tail=None,None for i in l: if i ==-1: break new_node=Node(i) if head is None: head=new_node tail=new_node else: tail.next=new_node tail=new_node return headhead1=take_input([10,20,30,40,50,60,70])head2=take_input([10,30,50,80,90])print_ll(union(head1,head2)) # This code is contributed by Shubham Setia |
C#
using System;class Node { public int data; public Node next; public Node(int data) { this.data = data; this.next = null; }}class Program { // function to print linked list static void printLinkedList(Node head) { Node temp = head; while (temp != null) { Console.Write(temp.data + "-->"); temp = temp.next; } Console.Write("None"); } // function to get union of two linked lists static Node getUnion(Node ll1, Node ll2) { Node tail = null; Node head = null; while (ll1 != null || ll2 != null) { if (ll1 == null) { if (tail == null) { tail = new Node(ll2.data); head = tail; } else { tail.next = new Node(ll2.data); tail = tail.next; } ll2 = ll2.next; } else if (ll2 == null) { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; } else { if (ll1.data < ll2.data) { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; } else if (ll1.data > ll2.data) { if (tail == null) { tail = new Node(ll2.data); head = tail; } else { tail.next = new Node(ll2.data); tail = tail.next; } ll2 = ll2.next; } else { if (tail == null) { tail = new Node(ll1.data); head = tail; } else { tail.next = new Node(ll1.data); tail = tail.next; } ll1 = ll1.next; ll2 = ll2.next; } } } return head; } // main function to test the code static void Main(string[] args) { // create first linked list Node head1 = new Node(10); head1.next = new Node(20); head1.next.next = new Node(30); head1.next.next.next = new Node(40); head1.next.next.next.next = new Node(50); head1.next.next.next.next.next = new Node(60); head1.next.next.next.next.next.next = new Node(70); // create second linked list Node head2 = new Node(10); head2.next = new Node(30); head2.next.next = new Node(50); head2.next.next.next = new Node(80); head2.next.next.next.next = new Node(90); Node head = getUnion(head1, head2); printLinkedList(head); Console.WriteLine(); }} |
Javascript
function merge(ll1, ll2) { if (!ll1) { return ll2; } if (!ll2) { return ll1; } let head, tail; if (ll1.data === ll2.data) { head = ll1; tail = ll1; ll1 = ll1.next; ll2 = ll2.next; } else if (ll1.data > ll2.data) { head = ll2; tail = ll2; ll2 = ll2.next; } else { head = ll1; tail = ll1; ll1 = ll1.next; } while (ll1 !== null && ll2 !== null) { if (ll1.data === ll2.data) { tail.next = ll1; tail = ll1; ll1 = ll1.next; ll2 = ll2.next; } else if (ll1.data > ll2.data) { tail.next = ll2; tail = ll2; ll2 = ll2.next; } else { tail.next = ll1; tail = ll1; ll1 = ll1.next; } } if (ll1 !== null) { tail.next = ll1; } if (ll2 !== null) { tail.next = ll2; } return head;}function mid_point_2(head) { if (!head) { return null; } let slow = head; let fast = head; while (fast.next !== null && fast.next.next !== null) { slow = slow.next; fast = fast.next.next; } return slow;}function merge_sort(head) { if (!head || !head.next) { return head; } let mid = mid_point_2(head); let head2 = merge_sort(mid.next); mid.next = null; let head1 = merge_sort(head); let final_head = merge(head1, head2); return final_head;}function union(head1, head2) { // return head of resultant linkedlist head1 = merge_sort(head1); head2 = merge_sort(head2); return merge(head1, head2);}// Driver Code Startsclass Node { constructor(data) { this.data = data; this.next = null; }}function print_ll(head) { let str = ''; while (head !== null) { str += head.data + '-->'; head = head.next; } console.log(str + 'None');}function take_input(l) { if (l.length === 0 || l[0] === -1) { return null; } let head = null; let tail = null; for (let i = 0; i < l.length; i++) { if (l[i] === -1) { break; } let new_node = new Node(l[i]); if (head === null) { head = new_node; tail = new_node; } else { tail.next = new_node; tail = new_node; } } return head;}let head1 = take_input([10, 20, 30, 40, 50, 60, 70]);let head2 = take_input([10, 30, 50, 80, 90]);print_ll(union(head1, head2)); |
Output
10-->20-->30-->40-->50-->60-->70-->80-->90-->None
Method 3 (Use Hashing):
Union (list1, list2)
Initialize the result list as NULL and create an empty hash table. Traverse both lists one by one, for each element being visited, look at the element in the hash table. If the element is not present, then insert the element into the result list. If the element is present, then ignore it.
Intersection (list1, list2)
Initialize the result list as NULL and create an empty hash table. Traverse list1. For each element being visited in list1, insert the element in the hash table. Traverse list2, for each element being visited in list2, look the element in the hash table. If the element is present, then insert the element to the result list. If the element is not present, then ignore it.
Both of the above methods assume that there are no duplicates.
C++
#include <iostream>#include <map>#include <unordered_set>using namespace std;class LinkedList {public: struct Node { int data; Node* next; Node(int d) : data(d) , next(nullptr) { } }; Node* head = nullptr; void printList() { Node* temp = head; while (temp != nullptr) { cout << temp->data << " "; temp = temp->next; } cout << endl; } void push(int new_data) { Node* new_node = new Node(new_data); new_node->next = head; head = new_node; } void append(int new_data) { if (head == nullptr) { Node* n = new Node(new_data); head = n; return; } Node* n1 = head; Node* n2 = new Node(new_data); while (n1->next != nullptr) { n1 = n1->next; } n1->next = n2; n2->next = nullptr; } bool isPresent(Node* head, int data) { Node* t = head; while (t != nullptr) { if (t->data == data) return true; t = t->next; } return false; } LinkedList getIntersection(Node* head1, Node* head2) { unordered_set<int> hset; Node* n1 = head1; Node* n2 = head2; LinkedList result; while (n1 != nullptr) { if (hset.find(n1->data) == hset.end()) { hset.insert(n1->data); } n1 = n1->next; } while (n2 != nullptr) { if (hset.find(n2->data) != hset.end()) { result.push(n2->data); } n2 = n2->next; } return result; } LinkedList getUnion(Node* head1, Node* head2) { map<int, int> hmap; Node* n1 = head1; Node* n2 = head2; LinkedList result; while (n1 != nullptr) { if (hmap.find(n1->data) != hmap.end()) { hmap[n1->data]++; } else { hmap[n1->data] = 1; } n1 = n1->next; } while (n2 != nullptr) { if (hmap.find(n2->data) != hmap.end()) { hmap[n2->data]++; } else { hmap[n2->data] = 1; } n2 = n2->next; } for (auto it = hmap.begin(); it != hmap.end(); it++) { result.append(it->first); } return result; }};int main(){ LinkedList llist1, llist2, intersection, union_list; llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersection = intersection.getIntersection( llist1.head, llist2.head); union_list = union_list.getUnion(llist1.head, llist2.head); cout << "First List is" << endl; llist1.printList(); cout << "Second List is" << endl; llist2.printList(); cout << "Intersection List is" << endl; intersection.printList(); cout << "Union List is" << endl; ; union_list.printList();}// This code is contributed by Gaurav_Arora |
Java
// Java code for Union and Intersection of two// Linked Listsimport java.util.HashMap;import java.util.HashSet;class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Utility function to print list */ void printList() { Node temp = head; while (temp != null) { System.out.print(temp.data + " "); temp = temp.next; } System.out.println(); } /* Inserts a node at start of linked list */ void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } public void append(int new_data) { if (this.head == null) { Node n = new Node(new_data); this.head = n; return; } Node n1 = this.head; Node n2 = new Node(new_data); while (n1.next != null) { n1 = n1.next; } n1.next = n2; n2.next = null; } /* A utility function that returns true if data is present in linked list else return false */ boolean isPresent(Node head, int data) { Node t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } LinkedList getIntersection(Node head1, Node head2) { HashSet<Integer> hset = new HashSet<>(); Node n1 = head1; Node n2 = head2; LinkedList result = new LinkedList(); // loop stores all the elements of list1 in hset while (n1 != null) { if (hset.contains(n1.data)) { hset.add(n1.data); } else { hset.add(n1.data); } n1 = n1.next; } // For every element of list2 present in hset // loop inserts the element into the result while (n2 != null) { if (hset.contains(n2.data)) { result.push(n2.data); } n2 = n2.next; } return result; } LinkedList getUnion(Node head1, Node head2) { // HashMap that will store the // elements of the lists with their counts HashMap<Integer, Integer> hmap = new HashMap<>(); Node n1 = head1; Node n2 = head2; LinkedList result = new LinkedList(); // loop inserts the elements and the count of // that element of list1 into the hmap while (n1 != null) { if (hmap.containsKey(n1.data)) { int val = hmap.get(n1.data); hmap.put(n1.data, val + 1); } else { hmap.put(n1.data, 1); } n1 = n1.next; } // loop further adds the elements of list2 with // their counts into the hmap while (n2 != null) { if (hmap.containsKey(n2.data)) { int val = hmap.get(n2.data); hmap.put(n2.data, val + 1); } else { hmap.put(n2.data, 1); } n2 = n2.next; } // Eventually add all the elements // into the result that are present in the hmap for (int a : hmap.keySet()) { result.append(a); } return result; } /* Driver program to test above functions */ public static void main(String args[]) { LinkedList llist1 = new LinkedList(); LinkedList llist2 = new LinkedList(); LinkedList union = new LinkedList(); LinkedList intersection = new LinkedList(); /*create a linked list 10->15->4->20 */ llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); /*create a linked list 8->4->2->10 */ llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersection = intersection.getIntersection(llist1.head, llist2.head); union = union.getUnion(llist1.head, llist2.head); System.out.println("First List is"); llist1.printList(); System.out.println("Second List is"); llist2.printList(); System.out.println("Intersection List is"); intersection.printList(); System.out.println("Union List is"); union.printList(); }}// This code is contributed by Kamal Rawal |
Python3
class LinkedList: class Node: def __init__(self, data): self.data = data self.next = None def __init__(self): self.head = None # head of list # Utility function to print list def printList(self): temp = self.head while temp: print(temp.data, end=" ") temp = temp.next print() # Inserts a node at start of linked list def push(self, new_data): new_node = self.Node(new_data) new_node.next = self.head self.head = new_node def append(self, new_data): if not self.head: n = self.Node(new_data) self.head = n return n1 = self.head n2 = self.Node(new_data) while n1.next: n1 = n1.next n1.next = n2 n2.next = None # A utility function that returns true if data is # present in linked list else return false def isPresent(self, head, data): t = head while t: if t.data == data: return True t = t.next return False def getIntersection(self, head1, head2): hset = set() n1 = head1 n2 = head2 result = LinkedList() # loop stores all the elements of list1 in hset while n1: if n1.data not in hset: hset.add(n1.data) n1 = n1.next while n2: if n2.data in hset: result.push(n2.data) n2 = n2.next return result def getUnion(self, head1, head2): hmap = {} n1 = head1 n2 = head2 result = LinkedList() # loop inserts the elements and the count of # that element of list1 into the hmap while n1: if n1.data in hmap: hmap[n1.data] += 1 else: hmap[n1.data] = 1 n1 = n1.next # loop further adds the elements of list2 with # their counts into the hmap while n2: if n2.data in hmap: hmap[n2.data] += 1 else: hmap[n2.data] = 1 n2 = n2.next list1 = [] for key, value in hmap.items(): # for _ in range(value): list1.append(key) list1 = set(list1) for i in list1: result.append(i) return result# Driver program to test above functionsllist1 = LinkedList()llist2 = LinkedList()intersection = LinkedList()union_list = LinkedList()# create a linked list 10->15->4->20llist1.push(20)llist1.push(4)llist1.push(15)llist1.push(10)# create a linked list 8->4->2->10 llist2.push(10)llist2.push(2)llist2.push(4)llist2.push(8)intersection = intersection.getIntersection( llist1.head, llist2.head)union_list = union_list.getUnion( llist1.head, llist2.head)print("First List is")llist1.printList()print("Second List is")llist2.printList()print("Intersection List is")intersection.printList()print("Union List is")union_list.printList() |
C#
// C# code for Union and Intersection of two// Linked Listsusing System;using System.Collections;using System.Collections.Generic;class LinkedList{ public Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } /* Utility function to print list */ void printList() { Node temp = head; while (temp != null) { Console.Write(temp.data + " "); temp = temp.next; } Console.WriteLine(); } /* Inserts a node at start of linked list */ void push(int new_data) { /* 1 & 2: Allocate the Node & Put in the data*/ Node new_node = new Node(new_data); /* 3. Make next of new Node as head */ new_node.next = head; /* 4. Move the head to point to new Node */ head = new_node; } public void append(int new_data) { if (this.head == null) { Node n = new Node(new_data); this.head = n; return; } Node n1 = this.head; Node n2 = new Node(new_data); while (n1.next != null) { n1 = n1.next; } n1.next = n2; n2.next = null; } /* A utility function that returns true if data is present in linked list else return false */ bool isPresent(Node head, int data) { Node t = head; while (t != null) { if (t.data == data) return true; t = t.next; } return false; } LinkedList getIntersection(Node head1, Node head2) { HashSet<int> hset = new HashSet<int>(); Node n1 = head1; Node n2 = head2; LinkedList result = new LinkedList(); // loop stores all the elements of list1 in hset while (n1 != null) { if (hset.Contains(n1.data)) { hset.Add(n1.data); } else { hset.Add(n1.data); } n1 = n1.next; } // For every element of list2 present in hset // loop inserts the element into the result while (n2 != null) { if (hset.Contains(n2.data)) { result.push(n2.data); } n2 = n2.next; } return result; } LinkedList getUnion(Node head1, Node head2) { // HashMap that will store the // elements of the lists with their counts SortedDictionary<int, int> hmap = new SortedDictionary<int, int>(); Node n1 = head1; Node n2 = head2; LinkedList result = new LinkedList(); // loop inserts the elements and the count of // that element of list1 into the hmap while (n1 != null) { if (hmap.ContainsKey(n1.data)) { hmap[n1.data]++; } else { hmap[n1.data]= 1; } n1 = n1.next; } // loop further adds the elements of list2 with // their counts into the hmap while (n2 != null) { if (hmap.ContainsKey(n2.data)) { hmap[n2.data]++; } else { hmap[n2.data]= 1; } n2 = n2.next; } // Eventually add all the elements // into the result that are present in the hmap foreach(int a in hmap.Keys) { result.append(a); } return result; } /* Driver program to test above functions */ public static void Main(string []args) { LinkedList llist1 = new LinkedList(); LinkedList llist2 = new LinkedList(); LinkedList union = new LinkedList(); LinkedList intersection = new LinkedList(); /*create a linked list 10->15->4->20 */ llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); /*create a linked list 8->4->2->10 */ llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); intersection = intersection.getIntersection(llist1.head, llist2.head); union = union.getUnion(llist1.head, llist2.head); Console.WriteLine("First List is"); llist1.printList(); Console.WriteLine("Second List is"); llist2.printList(); Console.WriteLine("Intersection List is"); intersection.printList(); Console.WriteLine("Union List is"); union.printList(); }}//This code is contributed by pratham76 |
Javascript
class Node { constructor(data) { this.data = data; this.next = null; } } class LinkedList { constructor() { this.head = null; } // Utility function to print list printList() { let temp = this.head; while (temp !== null) { process.stdout.write(temp.data + ' '); temp = temp.next; } console.log(); } push(newData) { const newNode = new Node(newData); newNode.next = this.head; this.head = newNode; } append(newData) { if (!this.head) { this.head = new Node(newData); return; } let current = this.head; while (current.next !== null) { current = current.next; } current.next = new Node(newData); } // A utility function that returns true if data is // present in linked list else return false isPresent(head, data) { let t = head; while (t !== null) { if (t.data === data) return true; t = t.next; } return false; } getIntersection(head1, head2) { const hset = new Set(); let n1 = head1; let n2 = head2; const result = new LinkedList(); // loop stores all the elements of list1 in hset while (n1 !== null) { if (!hset.has(n1.data)) { hset.add(n1.data); } n1 = n1.next; } // For every element of list2 present in hset // loop inserts the element into the result while (n2 !== null) { if (hset.has(n2.data)) { result.push(n2.data); } n2 = n2.next; } return result; } getUnion(head1, head2) { const hmap = new Map(); let n1 = head1; let n2 = head2; const result = new LinkedList(); // loop inserts the elements and the count of // that element of list1 into the hmap while (n1 !== null) { if (hmap.has(n1.data)) { hmap.set(n1.data, hmap.get(n1.data) + 1); } else { hmap.set(n1.data, 1); } n1 = n1.next; } // loop further adds the elements of list2 with // their counts into the hmap while (n2 !== null) { if (hmap.has(n2.data)) { hmap.set(n2.data, hmap.get(n2.data) + 1); } else { hmap.set(n2.data, 1); } n2 = n2.next; } for (const [key, value] of hmap.entries()) { for (let i = 0; i < value; i++) { result.append(key); } } return result; } } // Example usage const llist1 = new LinkedList(); const llist2 = new LinkedList(); const intersection = new LinkedList(); const union_List = new LinkedList(); llist1.push(20); llist1.push(4); llist1.push(15); llist1.push(10); llist2.push(10); llist2.push(2); llist2.push(4); llist2.push(8); const intersectionResult = intersection.getIntersection(llist1.head, llist2.head); const unionResult = union_List.getUnion(llist1.head, llist2.head); console.log('First List is'); llist1.printList(); console.log('Second List is'); llist2.printList(); console.log('Intersection List is'); intersectionResult.printList(); console.log('Union List is'); unionResult.printList(); |
Output
First List is 10 15 4 20 Second List is 8 4 2 10 Intersection List is 10 4 Union List is 2 4 8 10 15 20
Complexity Analysis:
- Time Complexity: O(m+n).
Here ‘m’ and ‘n’ are number of elements present in the first and second lists respectively.
For union: Traverse both the lists, store the elements in Hash-map and update the respective count.
For intersection: First traverse list-1, store its elements in Hash-map and then for every element in list-2 check if it is already present in the map. This takes O(1) time. - Auxiliary Space:O(m+n).
Use of Hash-map data structure for storing values.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
