Merge Two Sorted Linked List
Tags: c, array, linkedlist
Published: 2022-06-07 07:39:04

Suppose you are given two linked lists which are both sorted into ascending order, then you have to merge these two separate sorted (ascending) linked lists into one sorted linked list. 

For example if you have, 

Linked List 1 = 3, 4, 5

Linked List 2 = 7, 8, 9

then, you should write a  `merge function` for the above two linked list such that it will merge and return a single linked list as shown below,

Merged Linked list = 3, 4, 5, 7, 8, 9

## Steps to merge two sorted linked list :

* First create two separate sorted(ascending) linked lists.

*  Initialise two pointers `p` and `q` of type `struct node` to point the first node of each created sorted linked list. 

**Now write a `merge` function.** 

* If `p` is `NULL`, then return `q` i.e., return `list2` and if `q` is `NULL`, then return `p` i.e., return `list1`. 

*  Initialise a dummy pointer `sort` of type `struct node` to merge two linked list and also initialise another pointer `head3` to point the first node of resultant merged linked list.

* If both the list exists, then check is  `p->data <= q->data`. If yes, then dummy pointer `sort` will point to `p` and `p` is updated to `p->next` else `sort` will point `q` and `q` is updated to `q->next`.

* Make pointer `head3` to point to the node to which dummy pointer `sort` is pointing. This `head3` pointing node will be the first node of the resultant merged linked list .

**Note : At this point, pointer `sort` will be pointing to the node which contains the smallest data among the two list.  Pointers `p` or `q` will be pointing to the immediate next node of the node pointing to by `sort`.**

* Check `p->data <= q->data`. If yes, then create a link between a node pointing to by `sort` and a node pointing to by `p` and then update both the pointers by one node ahead else create a link between a node pointing to by `sort` and a node pointing to by `q` and then update both the pointers by one node ahead. Repeat this process until one of the linked list becomes `NULL`.  

* If `p` becomes `NULL` first then create a link between `sort` and `q`. 
If `q` becomes `NULL` first then create a link between `sort` and `p`. 

* Return `head3`.

* Display the merged sorted linked list. 

```
#include<stdio.h>
#include<stdlib.h>
 
struct node
{
	int data;
	struct node * next;
};
struct node * merge(struct node * p , struct node * q , struct node * sort)
{
	struct node *  head3;
	 
	if(p == NULL)
		return q;
	 	
	if(q == NULL)
		return p;
	 
	if(p && q)
	{
		if(p->data <= q->data)
		{
			sort = p;
			p = sort->next;
		}
		else
		{
			sort = q;
			q = sort->next;
		}
 
	}
 	
	head3 = sort;
 	
	while(p && q)
	{
		if(p->data <= q->data)
		{
			sort->next = p;
			sort = p;
			p = sort->next;
		}
		else
		{
			sort->next = q;
			sort = q;
			q = sort->next;
		}
	}
	
	if(p==NULL)
	{
		sort->next = q;
	}
 	
	if(q==NULL)
	{
		sort->next = p;
	}
 	
	return head3;	
}
 
int main()
{
	struct node * p=NULL , * q=NULL , * head1=NULL , * head2=NULL , * sort = NULL;
	int n1 , n2 , a;
	 
    printf("Enter the number of nodes in the first Linked List: ");
	scanf("%d",&n1);
	 
	printf("Enter the number of nodes in the second Linked List: ");
	scanf("%d",&n2);
	 
	if(n1 > 0)
	{
	printf("Enter the data1 of first Linked List: ");
	scanf("%d",&a);
	p = (struct node* )malloc(sizeof(struct node));
	p->data = a;
	p->next = NULL;
	head1 = p;
	}
	 
	for(int i=1; i<n1; i++)
	{
	    printf("Enter the data%d: ", i+1);
		scanf("%d",&a);
		q = (struct node* )malloc(sizeof(struct node));
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;		
	}
 
	if(n2 > 0)
	{
	printf("Enter the data1 of second Linked List: ");
	scanf("%d",&a);
	p = (struct node* )malloc(sizeof(struct node));
	p->data = a;
	p->next = NULL;
	head2 = p;
	}
 		
	for(int i=1;i<n2;i++)
	{
	    printf("Enter the data%d: ", i+1);
		scanf("%d",&a);
		q = (struct node* )malloc(sizeof(struct node));
		q->data = a;
		q->next = NULL;
		p->next = q;
		p = p->next;		
	}
	p = head1;
	q = head2;
	printf("\n First Linked List : ");
	while(p!=NULL)
	{
		printf("%d  ",p->data);
		p = p->next;
	}
 
	printf("\n Second Linked List: ");
	while(q!=NULL)
	{
		printf("%d  ",q->data);
		q = q->next;
	}
 
	p = head1;
	q = head2;
	sort = merge(p  , q , sort);
	 
    printf("\n");
	printf("\n Sorted Merged Linked List: ");
	while(sort!=NULL)
	{
		printf("%d  ",sort->data);
		sort = sort->next;
	}
	return 0;
}
```

 **For more detail watch this  [video](https://www.youtube.com/watch?v=j_UNYW6Ap0k).**

**I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.**