/*Merging of sorted linked lists */
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{ int data;
struct node *next;
}node;
node *merge(node *l1,node *l2);
node *create_normal();
node *create_sorted();
void print(node *head);
void sort(node *head);
void main()
{
int op1,op2;
node *head1,*head2,*head3;
// Accepting second linked list
printf("\n Enter first Linked list\n");
printf("\nSelect option");
printf("\n 1)Accepting data to create normal linked list and then sort it");
printf("\n 2)Accepting data and sorting it while creation:\n");
scanf("%d",&op1);
switch(op1)
{
case 1:printf("\n\nCreating Normal(unsortrd) linked list \n");
head1=create_normal();
printf("\nFirst LInked list(Before Sorting):");
print(head1);
sort(head1);
printf("\nFirst Linked list(After Sorting):");
print(head1);
break;
case 2:printf("\n\nCreating sorted linked list \n");
head1=create_sorted();
printf("\nFirst Linked list:");
print(head1);
break;
default : printf("\n Invalid input ");
exit(0);
}
// Accepting second linked list
printf("\n Enter second Linked list\n");
printf("\nSelect option");
printf("\n 1)Accepting data to create normal linked list and then sort it");
printf("\n 2)Accepting data and sorting it while creation:\n");
scanf("%d",&op2);
switch(op2)
{
case 1:printf("\n\nCreating Normal(unsortrd) linked list \n");
head2=create_normal();
printf("\nSecond LInked list(Before Sorting):");
print(head2);
sort(head2);
printf("\nSecond Linked list(After Sorting):");
print(head2);
break;
case 2:printf("\n\nCreating sorted linked list \n");
head2=create_sorted();
printf("\nSecond Linked list:");
print(head2);
break;
default : printf("\n Invalid input ");
exit(0);
}
head3=merge(head1,head2);
printf("\nFinal List:");
print(head3);
}
node *merge(node *l1,node *l2)
{ node *l,*p;
l=NULL;
if(l1==NULL)
return(l2);
if(l2==NULL)
return(l1);
//insert the first data
if(l1->data<l2->data)
{
l=p=l1;
l1=l1->next;
}
else
{
l=p=l2;
l2=l2->next;
}
while(l1!=NULL && l2!=NULL)
{
if(l1->data < l2->data)
{
p->next=l1;
l1=l1->next;
p=p->next;
}
else
{
p->next=l2;
l2=l2->next;
p=p->next;
}
}
if(l1!=NULL)
p->next=l1;
else
p->next=l2;
return(l);
}
node *create_normal()
{
node *head=NULL,*p;
int n,x,i;
printf("\nNumber of nodes:");
scanf("%d",&n);
printf("\nEnter data:");
for(i=1;i<=n;i++)
{
scanf("%d",&x);
if(head==NULL)
{
p=head=(node*)malloc(sizeof(node));
p->next=NULL;
}
else
{
p->next=(node*)malloc(sizeof(node));
p=p->next;
p->next=NULL;
}
p->data=x;
}
return(head);
}
node *create_sorted()
{ node *head=NULL,*p,*q;
int n,x,i;
printf("\nNumber of nodes:");
scanf("%d",&n);
printf("\nEnter data:");
for(i=1;i<=n;i++)
{ scanf("%d",&x);
p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(head==NULL || x<head->data)
{ p->next=head;
head=p;
}
else
{ q=head;
while(q->next !=NULL && x>q->next->data)
q=q->next;
p->next=q->next;
q->next=p;
}
}
return(head);
}
void print(node *head)
{
printf("\n");
while(head != NULL)
{
printf("%5d",head->data);
head=head->next;
}
}
void sort(node *head)
{
int i,j,n,temp;
node *p;
/*counting number of nodes*/
for(n=0,p=head;p!=NULL;p=p->next)
n++;
for(i=1;i<n;i++)
{
p=head;
for(j=0;j<n-i;j++)
{
if(p->data > p->next->data)
{
temp=p->data;
p->data=p->next->data;
p->next->data=temp;
}
p=p->next;
}
}
}
No comments:
Post a Comment