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
pandqof typestruct nodeto point the first node of each created sorted linked list.
Now write a merge function.
If
pisNULL, then returnqi.e., returnlist2and ifqisNULL, then returnpi.e., returnlist1.Initialise a dummy pointer
sortof typestruct nodeto merge two linked list and also initialise another pointerhead3to 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 pointersortwill point topandpis updated top->nextelsesortwill pointqandqis updated toq->next.Make pointer
head3to point to the node to which dummy pointersortis pointing. Thishead3pointing 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 bysortand a node pointing to bypand then update both the pointers by one node ahead else create a link between a node pointing to bysortand a node pointing to byqand then update both the pointers by one node ahead. Repeat this process until one of the linked list becomesNULL.If
pbecomesNULLfirst then create a link betweensortandq.
IfqbecomesNULLfirst then create a link betweensortandp.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.
I own a website www.coderlogs.com where in I write similar blogs so do visit the website for more such blog posts.
Top comments (0)