#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node{
	int val;
	struct node *next;
	}*p[2],*q[2],*start[2];

int total[2];

void accept(int),display(int,int),merge(),sort(int),del(int);

int main()
{
int j,i;
clrscr();
for(i=0;i<2;i++)
{
	accept(i);
	sort(i);
	display(i,0);
	getch();
}
merge();
sort(0);
display(0,1);
getch();
return 0;
}

void accept(int l)
{
int i,j,val;
start[l]=NULL;
printf("\n\nEnter Total Nodes in %d List : ",l+1);
scanf("%d",&total[l]);
for(i=0;i<total[l];i++)
{
	p[l]=malloc(sizeof(struct node));
	printf("Enter %d Element : ",i+1);
	scanf("%d",&val);
	p[l]->val=val;
	if(start[l]==NULL)
	{
		start[l]=p[l];
	}
	else
	{
		q[l]=start[l];
		while(q[l]->next!=NULL)
			q[l]=q[l]->next;
		q[l]->next=p[l];
	}
	p[l]->next=NULL;
}
}

void sort(int no)
{
struct node *temp;
q[1]=NULL;
while (q[1]!=start[no]->next)
{
	p[1]=p[0]=start[no];
	q[0]=p[0]->next;
	while(p[0]!=q[1])
	{
		if(p[0]->val>q[0]->val)
		{
			if(p[0]==start[no])
			{
				temp=q[0]->next;
				q[0]->next=p[0];
				p[0]->next=temp;
				start[no]=q[0];
				p[1]=q[0];
			}
			else
			{
				temp=q[0]->next;
				q[0]->next=p[0];
				p[0]->next=temp;
				p[1]->next=q[0];
				p[1]=q[0];
			}
		}
		else
		{
			p[1]=p[0];
			p[0]=p[0]->next;
		}
		q[0]=p[0]->next;
		if(q[0]==q[1])
			q[1]=p[0];
	}
}
}


void display(int l,int ans)
{
int i;
p[l]=start[l];
if(ans==0)
	printf("\n%d Link List\n",l+1);
else
	printf("\n\nMerged Link List:\n");
for(i=0;i<total[l];i++)
{
	printf(" %d ",p[l]->val);
	p[l]=p[l]->next;
}
}

void merge()
{
int i,j;
q[0]=start[0];
for(i=0;i<total[0];i++)
{
	q[1]=start[1];
	for(j=0;j<total[1];j++)
	{
		if(q[0]->val==q[1]->val)
		{
			del(q[1]->val);
			total[1]--;
		}
		q[1]=q[1]->next;
	}
	q[0]=q[0]->next;
}
q[0]=start[0];
while(q[0]->next!=NULL)
	q[0]=q[0]->next;
q[0]->next=start[1];
total[0]=total[0]+total[1];
}

void del(int no)
{
int i,j,found=0;
p[1]=start[1];
if(start[1]->val==no)
{
	start[1]=p[1]->next;
}
else
{
	while((p[1]->val)!=no)
		p[1]=p[1]->next;
	p[0]=start[1];
	while(p[0]->next!=p[1])
		p[0]=p[0]->next;
	p[0]->next=p[1]->next;
	p[1]->next=NULL;
}
free(p[1]);
}