#include<stdio.h>
#include<stdlib.h>


typedef struct node *ptr;
typedef struct node{
	int data;
	ptr next;
}node;


ptr list_1,list_2,list_3;


void dimiourgia(ptr *list)
{
	*list=NULL;
}

void insert(ptr *list,int data)
{
	ptr temp=malloc(sizeof(node));
	temp->data=data;
	
	
	if(*list==NULL)
	{
		temp->next=*list;
		*list=temp;
	}

	else{
		ptr cur1;
		
		cur1=*list;
		
		if(cur1->data>=data)
		{
			temp->next=*list;
			*list=temp;
		}
		else{
			while(cur1->data<=data && cur1->next!=NULL)cur1=cur1->next;
			
			if(cur1->next==NULL && cur1->data<=data)
			{
				temp->next=cur1->next;
				cur1->next=temp;
			}
			else if((cur1->next==NULL && cur1->data>=data) || (cur1->next!=NULL && cur1->data>=data))
			{
				ptr cur2=*list;
				while(cur2->next!=cur1)cur2=cur2->next;
				temp->next=cur2->next;
				cur2->next=temp;
			}
		}
		
	}


}

void run(ptr list)
{
	while(list!=NULL)
	{
		printf("%d ",list->data);
		list=list->next;
	}
	printf("\n");
}

int main(void)
{
	int i;
	
	dimiourgia(&list_1);
	dimiourgia(&list_2);
	dimiourgia(&list_3);
	
	srand(time(0));
	
	for(i=1;i<=4;i++)
	{
		insert(&list_1,rand()%20);
	}
	printf("------list_1------\n");
	run(list_1);
	
	
	for(i=1;i<=4;i++)
	{
		insert(&list_2,rand()%20);
	}
	printf("------list_2------\n");
	run(list_2);
	
	
	ptr cur1=list_1;//0 4 6 8
	ptr cur2=list_2;//12 14 16 18
	
	while(cur1!=NULL && cur2!=NULL)
	{
		if(cur1->data<=cur2->data)
		{
			insert(&list_3,cur1->data);
			cur1=cur1->next;	
		}
		else if(cur1->data>cur2->data)
		{
			insert(&list_3,cur2->data);
			cur2=cur2->next;	
		}
	}
	
	while(cur1!=NULL)
	{
		insert(&list_3,cur1->data);
		cur1=cur1->next;	
	}
	while(cur2!=NULL)
	{
		insert(&list_3,cur2->data);
		cur2=cur2->next;	
	}
	
	printf("\n------list_3------\n");
	run(list_3);
	printf("\n");
	return 0;
}