Home » C++ programs

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

In this article, we are going to see how to find union of two linked list efficiently using merge sorting?
Submitted by Radib Kar, on December 27, 2018

Problem statement: 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

Solution

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 complexity. m, n=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:
  3. 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
    
  4. 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




Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.