Home » Data Structure

Implement Union and Intersection of Two Sorted Linked Lists

Last Updated : December 02, 2025

Introduction

In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions.

Union of two linked lists can be found by using merging the lists in a sorted manner.

Union of Two Sorted Linked Lists

The intersection of the two lists can be found by only taking common elements while merging the two lists.

Intersection of Two Sorted Linked Lists

It has been assumed that the linked lists are sorted.

Algorithms for Union and Intersection of Two Sorted Linked Lists

1. Union(L1,L2)

1) Declare node pointer output, output Tail as NULL
2) Repeat steps 3 to 9 while L1!=NULL AND L2!=NULL
3) Make a newNode and set its next = NULL
4) If L1->data < L2->data then
    Set newNode->data = L1->data
    Set L1 = L1->next
5) Else if L1->data > L2->data then
    Set newNode->data = L2->data
    L2 = L2->next
6) Else
    i) Set Data = L1->data
    ii) Set newNode->data = Data
    iii) Repeat steps a) and b) 
    while L1!=NULL AND L2!=NULL AND L1->data == Data AND L2->data == Data
        a) Set L1 = L1->next
        b) Set L2 = L2->next

7) If output == NULL then
    Set Output = outputTail = newNode

8) Else
    a) Set outputTail->next = newNode
    b) Set outputTail = outputTail->next
    9) Repeat steps 10 to 14 while L1!=NULL
10) Make a newNode
11) Set outputTail->next = newNode
12) Set outputTail = outputTail->next
13) Set outputTail->data = L1->data
14) Set L1 = L1->next
    Repeat steps 15 to 19 while L2!=NULL
15) Make a newNode
16) Set outputTail->next = newNode
17) Set outputTail = outputTail->next
18) Set outputTail->data = L2->data
19) Set L2 = L2->next
    Return output

2. Intersection(L1,L2)

1.	If L1 or L2 is NULL then return NULL
2.	Declare node pointers output, outputTail as null.
3.	Repeat steps 4 to 6 while L1!=NULL AND L2!=NULL
4.	If L1->datadata then
    Set L1 = L1->next
5.	Else If L2->datadata then
    Set L2 = L2->next
6.	Else
    a)	Declare and set data = L1->data
    b)	Make a newNode
    c)	Set newNode->data = data and newNode->next = NULL
    d)	If output == null then
        i.	Set output = outputTail = newNode
    e)	Else
        i.	Set outputTail->next = newNode
        ii.	Set outputTail = outputTail->next
    f)	Repeat steps i and ii 
    while L1!=NULL AND L2!=NULL AND L1->data == data AND L2->data == data
        i.	Set L1 = L1->next
        ii.	Set L2 = L2->next

C++ Code to Implement Union and Intersection of Two Sorted Linked Lists

#include <stdio.h>
#include <stdlib.h>

struct node{
	struct node*next;
	int data;
};

struct node * Union(struct node * L1, struct node * L2){
	struct node * output = NULL;
	struct node * outTail = NULL;
	while(L1&&L2){
		struct node * newNode = (struct node *) malloc(sizeof(struct node));
		newNode->next = NULL;
		if(L1->data<L2->data){
			newNode->data = L1->data;
			L1 = L1->next;
		}
		else if(L1->data>L2->data){
			newNode->data = L2->data;
			L2 = L2->next;
		}
		else{
			int data = L1->data;
			newNode->data = data;
			while(L1 && L2 && L1->data == data && L2->data == data){
				L1 = L1->next;
				L2 = L2->next;
			}
		}
		if(!output)
			output = outTail = newNode;
		else{
			outTail->next = newNode;
			outTail = outTail->next;
		}
	}
	while(L1){
		outTail->next = (struct node *) malloc(sizeof(struct node));
		outTail = outTail->next;
		outTail->data = L1->data;
		L1 = L1->next;
	}
	while(L2){
		outTail->next = (struct node *) malloc(sizeof(struct node));
		outTail = outTail->next;
		outTail->data = L2->data;
		L2 = L2->next;
	}
	outTail->next = NULL;
	return output;
}

struct node * intersection(struct node * L1, struct node* L2){
	if(L1 == NULL || L2 == NULL)
		return NULL;
	struct node * output = NULL;
	struct node * outTail = NULL;
	while(L1&&L2){
		if(L1->data<L2->data){
			L1 = L1->next;
		}
		else if(L2->data<L1->data){
			L2 = L2->next;
		}
		else{
			int data = L1->data;
			struct node * newNode = (struct node *) malloc(sizeof(struct node));
			newNode->data = data;
			newNode->next = NULL;
			if(output == NULL){
				outTail = output = newNode;
			}
			else{
				outTail->next = newNode;
				outTail = outTail->next;
			}
			while(L1 && L2 && L1->data == data && L2->data == data){
				L1 = L1->next;
				L2 = L2->next;
			}
		}
	}
	return output;
}

struct node * createList(int listNum){
	struct node * list = NULL;
	struct node * list_tail = NULL;
	printf("Enter elements of List %d in increasing order\n",listNum);
	char ch = 'y';
	do{
		int data;
		printf("Enter element : ");
		scanf("%d",&data);
		struct node * newNode = (struct node *) malloc(sizeof(struct node));
		newNode->data = data;
		newNode->next = NULL;
		if(list == NULL){
			list = list_tail = newNode;
		}
		else{
			list_tail->next = newNode;
			list_tail = list_tail->next;
		}
		printf("Would you like to insert another element [Y/N] : ");
		scanf(" %c",&ch);
	}while(ch == 'y' || ch == 'Y');
	
	return list;
}

void print(struct node * list){
	if(list == NULL){
		printf("Empty List\n");
		return;
	}
	while(list!=NULL){
		printf("%d ",list->data);
		list = list->next;
	}
	printf("\n");
}

int main() {
	struct node * L1 = NULL;
	struct node * L2 = NULL;
	struct node * L3 = NULL;
	struct node * L4 = NULL;
	L1 = createList(1);
	L2 = createList(2);
	printf("List 1 : ");
	print(L1);
	printf("List 2 : ");
	print(L2);
	printf("Union : ");
	L3 = Union(L1, L2);
	print(L3);
	printf("Intersection : ");
	L4 = intersection(L1, L2);
	print(L4);
	return 0;
}

Output

Enter elements of List 1 in increasing order 
Enter element : 1
Would you like to insert another element [Y/N] : Y 
Enter element : 4
Would you like to insert another element [Y/N] : Y 
Enter element : 9
Would you like to insert another element [Y/N] : Y 
Enter element : 27 
Would you like to insert another element [Y/N] : N 
Enter elements of List 2 in increasing order 
Enter element : 4
Would you like to insert another element [Y/N] : Y 
Enter element : 9
Would you like to insert another element [Y/N] : Y 
Enter element : 18 
Would you like to insert another element [Y/N] : Y 
Enter element : 22 
Would you like to insert another element [Y/N] : Y 
Enter element : 30 
Would you like to insert another element [Y/N] : N 
List 1 : 1 4 9 27
List 2 : 4 9 18 22 30
Union : 1 4 9 18 22 27 30
Intersection : 4 9