Q:

C++ program to find Union of two single Linked Lists

0

Write a C++ program to find the union of two single linked lists.

Example:

    Let the first linked list be:
    5->4->3->6->1->NULL

    Let the second linked list to be:
    3->8->9->12->1->NULL

    So there union is:
    5->4->3->6->1->8->9->12->NULL

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Brute force approach:

One technique can be to include all the nodes of a linked list and for other linked check whether nodes are already appended or not. Such an approach takes O(m*n) times complexitymn=length of linked lists.

Efficient approach:

Efficient approach use to use merge sort.

    1. Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
    2. Scan each linked list and build union according to following:
IF (list1->data < list2->data)
	Createnode(list1->data) && append node to the union list
	Traverse list1 by one step( list1=list1->next)
ELSE IF(list1->data ==list2->data)
	Createnode(list1->data) && append nodeto the union list
	Traverse list1 by one step( list1=list1->next)
	Traverse list2 by one step( list2=list2->next)
ELSE//list1->data >list2->data
	Createnode(list2->data) && append node to the union list
	Traverse list2 by one step( list2=list2->next)
END IF-ELSE
  1. Display the union list

C++ implementation to find Union of two single Linked Lists

#include<bits/stdc++.h>
using namespace std;

class node{
    public:
	int data; // data field
	struct node *next;
};

void display(class node* head){
	node* current=head; // current node set to head
	while(current!=NULL){ //traverse until current node isn't NULL
		printf("%d ",current->data);
		current=current->next; // go to next node
	}
}

node* creatnode(int d){
	node* temp=(node*)malloc(sizeof(node));
	temp->data=d;
	temp->next=NULL;
	return temp;
}
node* mergeList(node* split1,node* split2){
    
    node* newhead=NULL;
    //base cases
    if(split1==NULL)
    return split2;
    if(split2==NULL)
    return split1;
    
    if(split1->data<=split2->data){
        newhead=split1;
        newhead->next=mergeList(split1->next,split2);
    }
    else{
        newhead=split2;
        newhead->next=mergeList(split1,split2->next);
    }
    
    
    return newhead;
    
}



void splitList(node* head,node** split1,node** split2){
    
    node* slow=head;
    node* fast=head->next;
    
    while(fast!=NULL){
        fast=fast->next;
        if(fast!=NULL){
            slow=slow->next;
            fast=fast->next;
        }
    }
    
    *split1=head;
    *split2=slow->next;
    //spliting
    slow->next=NULL;
}

void mergeSort(node** refToHead){
    node* head=*refToHead;
    node* split1,*split2;
    //base case
    if(head==NULL || head->next==NULL){
        return;
    }
    //split the list in two halves
    splitList(head,&split1,&split2);
    //recursively sort the two halves
    mergeSort(&split1);
    mergeSort(&split2);
    
    *refToHead=mergeList(split1,split2);
    
    return;
    
}


node* findUnion(node* head1, node* head2){
    
    if(head1==NULL && head2==NULL)
    return NULL;
    
    node* head3;
    if(head1->data<head2->data){
            
        head3=creatnode(head1->data);
        head1=head1->next;
    }
    else if(head1->data==head2->data){
            
        head3=creatnode(head1->data);
    
        head1=head1->next;
        head2=head2->next;
    }
    else{
        
        head3=creatnode(head2->data);
        head2=head2->next;
    }
    node* temp=head3;
    while( head1!=NULL && head2!=NULL){
        
        if(head1->data<head2->data){
            temp->next=creatnode(head1->data);
            temp=temp->next;
            head1=head1->next;
        }
        else if(head1->data==head2->data){
            
            temp->next=creatnode(head1->data);
            
            temp=temp->next;
            
            head1=head1->next;
            head2=head2->next;
        }
        else{
            temp->next=creatnode(head2->data);
            temp=temp->next;
            head2=head2->next;
        }
        
        
    }
    
    while(head1!=NULL){
        temp->next=creatnode(head1->data);
        temp=temp->next;
        head1=head1->next;
    }
    while(head2!=NULL){
        temp->next=creatnode(head2->data);
        temp=temp->next;
        head2=head2->next;
    }
    
    return head3;
    
}

int main(){
	printf("creating the linked list by inserting new nodes at the end\n");
	printf("enter 0 to stop building the list, else enter any integer\n");
	int k;
	node* curr,*temp;
	cout<<"enter list1...\n";
	scanf("%d",&k);
	node* head1=creatnode(k); //buliding list, first node
	scanf("%d",&k);
	temp=head1;

	///////////////////inserting at the end//////////////////////
	while(k){
		curr=creatnode(k);
		temp->next=curr;//appending each node
		temp=temp->next;
		scanf("%d",&k);
	}
	cout<<"displaying list1...\n";
	display(head1); // displaying the list
	cout<<"\nenter list2...\n";
	scanf("%d",&k);
	node* head2=creatnode(k); //buliding list, first node
	scanf("%d",&k);
	temp=head2;

	///////////////////inserting at the end//////////////////////
	while(k){
		curr=creatnode(k);
		temp->next=curr;//appending each node
		temp=temp->next;
		scanf("%d",&k);
	}
	cout<<"displaying list1...\n";
	display(head2);
	
	//sort both the lists
	mergeSort(&head1);
	mergeSort(&head2);
	
	
	cout<<"\ndisplaying their union...\n";
	
	node* head3=findUnion(head1,head2);
	
	display(head3);
	return 0;
}

Output

creating the linked list by inserting new nodes at the end
enter 0 to stop building the list, else enter any integer
enter list1...
5 4 3  6 1 0
displaying list1...
5 4 3 6 1
enter list2...
3 8 9 12 1 0
displaying list1...
3 8 9 12 1
displaying their union...
1 3 4 5 6 8 9 12

Example with explanation:

 
First linked list: 5->4->3->6->1->NULL
Second linked list:3->8->9->12->1->NULL

After applying merge sort:
First linked list: 1->3->4->5->6->NULL
Second linked list: 1->3->8->9->12->NULL
---------------------------------------------------------

//for better understanding nodes are represented only by respective values
head1=1
head2=1
FindUnion(1,1):

0th iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=1
thus head3(head of union list) =1
temp=head3=1
union list up to now:
1->NULL
head1=1->next=3;
head2=1->next=3;

1st iteration
head1!=NULL&&head2!=NULL
head1->data==head2->data //=3
thus temp->next =3
temp=temp->next=3;
union list up to now:
1->3->NULL
head1=3->next=4;
head2=3->next=8;

2nd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //4<8
thus temp->next =head1->data=4
temp=temp->next=4;
union list up to now:
1->3->4->NULL

head1=4->next=5;

3rd iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //5<8
thus temp->next =head1->data=5
temp=temp->next=5;
union list up to now:
1->3->4->5->NULL
head1=5->next=6;

4th iteration
head1!=NULL&&head2!=NULL
head1->data<head2->data //6<8
thus temp->next =head1->data=6
temp=temp->next=6;
union list up to now:
1->3->4->5->6->NULL
head1=6->next=NULL;

5th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=8
temp=temp->next=8;
union list up to now:
1->3->4->5->6->8->NULL
head2=8->next=9;

6th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=9
temp=temp->next=9;
union list up to now:
1->3->4->5->6->8->9->NULL
head2=9->next=12;

7th iteration
head1 ==NULL
head2!=NULL
thus temp->next =head2->data=12
temp=temp->next=12;
union list up to now: 1->3->4->5->6->8->9->12->NULL

head2=12->next=NULL;

8th iteration:
head1==NULL 
head2==NULL
thus no more scanning, union list is built

union: 1->3->4->5->6->8->9->12->NULL
Head3 at 1

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Data Structure programs using C and C++ (Linked List Programs)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Find intersection of two linked lists using C++ pr... >>
<< Pair wise swap elements in a linked list using C++...