C++ program to find union of two single linked lists

Find union of two single linked lists: In this tutorial, we will learn how to find the union of two single linked lists with the help of multiple approaches using the C++ programs? By Radib Kar Last updated : August 01, 2023

Problem statement

Given two singly linked lists, write a C++ program to find the union of two given singly-linked lists.

Consider the below example with sample input and output:

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

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.

Sort both the linked list using merge sort. ( for detailed refer to: Merge sort for single linked lists)
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

Display the union list

C++ program 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)
{
    // current node set to head
    node* current = head;
    //traverse until current node isn't NULL
    while (current != NULL) {
        printf("%d ", current->data);
        // go to next node
        current = current->next;
    }
}

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);
    
    //buliding list, first node
    node* head1 = creatnode(k);
    scanf("%d", &k);
    temp = head1;

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

    //inserting at the end
    while (k) {
        curr = creatnode(k);
        //appending each node
        temp->next = curr;
        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):

0^th 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;

1^st 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;

2^nd 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;

3^rd 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;

4^th 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;

5^th 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;

6^th 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;

7^th 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;

8^th 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