- 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.
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.
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;
}
OutputEnter 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.
Let the two input linked list be LLOne and LLTwo and intersectionLL be the result linked list.
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.
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.