Suppose you are given two lists of integer numbers, where head1 and head2 contain address of first node of two lists respectively. Now create and return a new list representing the union of the two lists. The new list should be made with its own memory and the original lists should not be changed. Now Write a function unionList() that will return a list representing union of two linked list.
Example:
Input:
List1: 20 15 10 30 60
List2: 20 5 30 35 60 70 90
Output:
List3: 20 15 10 30 60 5 35 70 90
Solution:
Code:
#include <stdio.h>
#include <stdlib.h>
// create a node
struct Node {
int data;
struct Node* next;
};
// insert node
void insert(struct Node** head, int new_data)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* temp = *head;
new_node->data = new_data;
new_node->next = NULL;
if (*head == NULL)
{
*head = new_node;
return;
}
while (temp->next != NULL)
temp = temp->next;
temp->next = new_node;
return;
}
//combine two lists and insert into list3
struct Node* unionList(struct Node** head1,struct Node** head2,struct Node** head3)
{
struct Node *temp1=*head1,*temp2=*head2,*temp3=*head3;
while(temp1!=NULL)//traverse list1 and inserts elements in the list1 into list3
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = temp1->data;
new_node->next = NULL;
if(*head3==NULL)//for start node
{
*head3=new_node;
temp3=*head3;
}
else //traverse list
{
temp3->next=new_node;
temp3=new_node;
}
temp1=temp1->next;
}
while(temp2!=NULL)//traverse list2 and insert elements in list2 into list3
{
struct Node* temp=*head1;
int flag=0;
while(temp!=NULL)
{
if(temp2->data==temp->data)//for same data
{
flag=1;
break;
}
temp=temp->next;
}
if(flag==0)
{
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = temp2->data;
new_node->next = NULL;
temp3->next=new_node;
temp3=new_node;
}
temp2=temp2->next;
}
return *head3;
}// print list
void printList(struct Node* head)
{
struct Node *temp=head;
while (temp != NULL)
{
printf(" %d ", temp->data);
temp= temp->next;
}
}
int main() {
struct Node* head1 = NULL,*head2=NULL,*head3=NULL;
int n,m, v1,v2;
printf("How many value in List 1: ");
scanf("%d",&n);
for(int i =0;i<n;i++){
scanf("%d",&v1);
insert(&head1, v1);
}
printf("How many value in List 1: ");
scanf("%d",&m);
for(int i =0;i<m;i++){
scanf("%d",&v2);
insert(&head2, v2);
}
unionList(&head1,&head2,&head3);
printf("List1: ");
printList(head1);
printf("\nList2: ");
printList(head2);
printf("\nList3: ");
printList(head3);
}
