#include <stdio.h>
#include <malloc.h>
struct Node {
int data;
struct Node *next;
};
// a function to check if an element is there is a linked list or not
int is_present(struct Node* head, int element) {
if(head == NULL) {
return 0;
}
struct Node* ptr = head ;
while(ptr != NULL) {
if(ptr->data == element) {
return 1;
}
ptr = ptr->next;
}
return 0;
}
// function to insert a new node in a linked list
struct Node* insert(struct Node* head, int data) {
// allocating memory for a new node
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
// initiaising the valus of the linked list
new_node->data = data;
new_node->next = NULL;
// if the head is null then make the new node the head
if(head == NULL) {
head = new_node;
return head;
}
// otherwise take a pointer is taken which will comtain head
struct Node* ptr = head;
// then we loop till the end of the list
while (ptr->next != NULL) {
ptr = ptr->next;
}
// add element in the end of the list
ptr->next = new_node;
// return head
return head;
}
// function to print a linked list
void print(struct Node* head) {
printf("\n");
// if the head is null then the list is empty so we will print empty list
if(head == NULL) {
printf("Empty List");
return;
}
// take a pointer to the head of the linked list
struct Node* ptr = head;
// loop through the list and print all elements
while(ptr != NULL) {
printf("%d ", ptr->data);
ptr = ptr->next;
}
}
// a function that will create a new linked list and add all the elements
// comman to both the linked list in this new list
struct Node* intersection(struct Node* first, struct Node* second) {
// created head of a new linked list
struct Node* intersection = NULL;
// created pointer to the first linked list
struct Node* first_ptr = first;
// loop trough the first linked list
while(first_ptr != NULL) {
// created pointer to the second liked list
struct Node* second_ptr = second;
// loop through the second linked list
while(second_ptr != NULL) {
// if the element in the pointer of first linked list and second linked list
// then insert that element in the new linked list
if(first_ptr->data == second_ptr->data) {
intersection = insert(intersection, first_ptr->data);
}
second_ptr = second_ptr->next;
}
first_ptr = first_ptr->next;
}
// return the new linked list
return intersection;
}
// a function to return a new linked list which will be the union of the two linked list passed to it
struct Node* set_union(struct Node* first, struct Node* second) {
// create pointer to new linked list
struct Node* union_ptr = NULL;
// created pointer to the first linked list
struct Node* first_ptr = first;
// looping through the first linked list and adding all its elements in the new linked list
while(first_ptr != NULL) {
union_ptr = insert(union_ptr, first_ptr->data);
first_ptr = first_ptr->next;
}
// creating pointer to the second linked list
struct Node* second_ptr = second;
// looping through the second linked list
while(second_ptr != NULL) {
// if we find an element which is not already in the new linked list then we add it in the new linked list
if(is_present(union_ptr, second_ptr->data) == 0) {
union_ptr = insert(union_ptr, second_ptr->data);
}
second_ptr = second_ptr->next;
}
// return the union linked list
return union_ptr;
}
int main() {
struct Node* head = NULL;
head = insert(head, 10);
head = insert(head, 20);
head = insert(head, 4);
head = insert(head, 12);
head = insert(head, 65);
head = insert(head, 89);
head = insert(head, 1);
printf("\nList 1:");
print(head);
struct Node* head2 = NULL;
head2 = insert(head2, 1);
head2= insert(head2, 0);
head2 = insert(head2, 44);
head2 = insert(head2, 12);
head2 = insert(head2, 65);
head2 = insert(head2, 8);
head2 = insert(head2, 7);
printf("\nList 2:");
print(head2);
printf("\nIntersection: ");
print(intersection(head, head2));
printf("\nUnion: ");
print(set_union(head, head2));
return 0;
}