- Write a C program to find union and intersection of two linked list.
- Algorithm to find intersection and union of two singly linked list.

Given two singly linked list, we have to create two linked list which contains **union and intersection of both given linked list** respectively. For Example:

First Linked List 1-->2-->4-->9-->6-->8 Second Linked List 3-->1-->6-->10 Union of Both Linked List 1-->2-->4-->9-->6-->8-->3-->10 Intersection of Both Linked List 1-->6

**Method 1 : By Searching Nodes**

**Algorithm to find union of two linked list**

Let the two input linked list be LLOne and LLTwo and unionLL be the result linked list.

- Initialize unionLL with NULL.
- Traverse LLone and add all nodes to unionLL.
- Traverse LLTwo and check if a node of LLtwo is already present in unionLL then don't add this node otherwise add it in unionLL.

struct node* findunion(struct node *LLOne, struct node *LLTwo) { unionLL = NULL; /* Add all nodes of first Linked List to unionLL */ struct node *temp = LLOne; while(temp != NULL){ insert(&unionLL, temp->data); temp = temp->next; } /* Insert those nodes of LLTwo which is not present in LLOne */ while(LLTwo != NULL){ if(!search(LLOne, LLTwo->data)){ insert(&unionLL, LLTwo->data); } LLTwo = LLTwo->next; } return unionLL; }

**Algorithm to find intersection of two linked list**

Let the two input linked list be LLOne and LLTwo and intersectionLL be the result linked list.

- Initialize intersectionLL with NULL.
- Traverse LLOne, search each node of LLOne in LLTwo linked list. If found then add it to intersectionLL otherwise continue.

struct node* intersection(struct node *LLOne, struct node *LLTwo) { intersectionLL = NULL; /* Search every element of LLOne in LLTwo, If found then add it to intersection List */ while(LLOne != NULL){ if(search(LLTwo, LLOne->data)){ insert(&intersectionLL, LLOne->data); } LLOne = LLOne->next; } return intersectionLL; }

## C program to find union and Intersection of linked list

#include <stdio.h> #include <stdlib.h> /* A structure of linked list node */ struct node { int data; struct node *next; } *LLOne, *LLTwo, *unionLL, *intersectionLL; void initialize(){ LLOne = LLTwo = NULL; } /* Given a Inserts a node in front of a singly linked list. */ void insert(struct node **head, int num) { /* Create a new Linked List node */ struct node* newNode = (struct node*) malloc(sizeof(struct node)); newNode->data = num; /* Next pointer of new node will point to head node of linked list */ newNode->next = *head; /* make new node as new head of linked list */ *head = newNode; } /* Searches an element in Linked List by linearly traversing from head to tail */ int search(struct node *head, int num) { while (head != NULL) { if (head->data == num){ return 1; } head = head->next; } return 0; } /* Returns the union of two given linked list */ struct node* findunion(struct node *LLOne, struct node *LLTwo) { unionLL = NULL; /* Add all nodes of first Linked List to unionLL */ struct node *temp = LLOne; while(temp != NULL){ insert(&unionLL, temp->data); temp = temp->next; } /* Insert those nodes of LLTwo which is not present in LLOne */ while(LLTwo != NULL){ if(!search(LLOne, LLTwo->data)){ insert(&unionLL, LLTwo->data); } LLTwo = LLTwo->next; } return unionLL; } /* Returns the Linked List which contains common nodes of two given linked list */ struct node* intersection(struct node *LLOne, struct node *LLTwo) { intersectionLL = NULL; /* Search every element of LLOne in LLTwo, If found then add it to intersection List */ while(LLOne != NULL){ if(search(LLTwo, LLOne->data)){ insert(&intersectionLL, LLOne->data); } LLOne = LLOne->next; } return intersectionLL; } /* Prints a linked list from head node till tail node */ void printLinkedList(struct node *nodePtr) { while (nodePtr != NULL) { printf("%d", nodePtr->data); nodePtr = nodePtr->next; if(nodePtr != NULL) printf("-->"); } } int main() { int i, LLOneCount, LLTwoCount, temp; initialize(); /* Creating First linked List*/ printf("Enter number of nodes in first Linked List\n"); scanf("%d", &LLOneCount); printf("Enter %d integers\n", LLOneCount); for(i=0; i<LLOneCount; i++){ scanf("%d", &temp); insert(&LLOne, temp); } printLinkedList(LLOne); printf("\nEnter number of nodes in second Linked List\n"); scanf("%d", &LLTwoCount); printf("Enter %d integers\n", LLTwoCount); for(i=0; i<LLTwoCount; i++){ scanf("%d", &temp); insert(&LLTwo, temp); } printLinkedList(LLTwo); /* printing Union of two given linked list */ findunion(LLOne, LLTwo); intersection(LLOne, LLTwo); printf("\nUnion Linked List\n"); printLinkedList(unionLL); printf("\nIntersection Linked List\n"); printLinkedList(intersectionLL); return 0; }Output

Enter number of nodes in first Linked List 4 Enter 4 integers 1 2 3 4 4-->3-->2-->1 Enter number of nodes in second Linked List 4 Enter 4 integers 3 4 5 6 6-->5-->4-->3 Union Linked List 5-->6-->1-->2-->3-->4 Intersection Linked List 3-->4

**Method 1 : By Using Hashing**

**Algorithm to find union using Hash Table**

Let the two input linked list be LLOne and LLTwo and unionLL be the result linked list.

- Initialize unionLL with NULL and create an empty hash table.
- Traverse LLOne linked list and for every node if node's data already exists in hash table then continue otherwise add it in Hash table and unionLL.
- Traverse LLTwo linked list and for every node if node's data already exists in hash table then continue otherwise add it in Hash table and unionLL.

**Algorithm to find intersection using Hash Table**

Let the two input linked list be LLOne and LLTwo and intersectionLL be the result linked list.

- Initialize intersectionLL with NULL and create an empty hash table.
- Traverse LLOne linked list and put data of each node in a Hash table.
- Traverse LLTwo linked list and check for every node if node's data already exists in hash table then continue otherwise add it in intersectionLL.

**NODE**: Above methods assumes No Duplicate in linked list.