/*
Write a program of merging two sorted single linked lists.
*/
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
};
struct node *create(struct node *start);
struct node *insert_s(struct node *start,int data);
struct node *insert(struct node *start,int data);
void display(struct node *start );
void merge(struct node *p1,struct node *p2);
main()
{
struct node *start1=NULL,*start2=NULL;
start1=create(start1);
start2=create(start2);
printf("List1 : ");
display(start1);
printf("List2 : ");
display(start2);
merge(start1, start2);
}
void merge(struct node *p1,struct node *p2)
{
struct node *start3;
start3=NULL;
while(p1!=NULL && p2!=NULL)
{
if(p1->info < p2->info)
{
start3=insert(start3,p1->info);
p1=p1->link;
}
else if(p2->info < p1->info)
{
start3=insert(start3,p2->info);
p2=p2->link;
}
else if(p1->info==p2->info)
{
start3=insert(start3,p1->info);
p1=p1->link;
p2=p2->link;
}
}
/*If second list has finished and elements left in first list*/
while(p1!=NULL)
{
start3=insert(start3,p1->info);
p1=p1->link;
}
/*If first list has finished and elements left in second list*/
while(p2!=NULL)
{
start3=insert(start3,p2->info);
p2=p2->link;
}
printf("Merged list is : ");
display(start3);
}
struct node *create(struct node *start )
{
int i,n,data;
printf("Enter the number of nodes : ");
scanf("%d",&n);
start=NULL;
for(i=1;i<=n;i++)
{
printf("Enter the element to be inserted : ");
scanf("%d",&data);
start=insert_s(start, data);
}
return start;
}
struct node *insert_s(struct node *start,int data)
{
struct node *p,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
/*list empty or data to be added in beginning */
if(start==NULL || data<start->info)
{
tmp->link=start;
start=tmp;
return start;
}
else
{
p=start;
while(p->link!=NULL && p->link->info < data)
p=p->link;
tmp->link=p->link;
p->link=tmp;
}
return start;
}
struct node *insert(struct node *start,int data)
{
struct node *p,*tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
/*If list is empty*/
if(start==NULL)
{
tmp->link=start;
start=tmp;
return start;
}
else /*Insert at the end of the list*/
{
p=start;
while(p->link!=NULL)
p=p->link;
tmp->link=p->link;
p->link=tmp;
}
return start;
}
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf("List is empty\n");
return;
}
p=start;
while(p!=NULL)
{
printf("%d ",p->info);
p=p->link;
}
printf("\n");
}
8 Comments
This comment has been removed by the author.
ReplyDeletewhy did you wrote it as "struct node *insert(ENTRY *start,int data) " instead of "int insert(ENTRY *start, int data)" , coz its works fine when i change it into int. Tnanks for the program btw, helps me alot.
ReplyDeleteThank you so much. It helped us a lot!
ReplyDeleteFALA TI MNOGU BRAT!:)))
ReplyDeleteHelped alot , Thanks for sharing
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDelete