#include<iostream>
using namespace std;

// Basic Template for Linked-List Node
struct node
{
	int data;
	struct node *next;
}*p, *q, *m;


// Add a New Node to List-1
void add_list1(int number)
{
	struct node* temp = p, *r, *t2;
	r = (struct node*)new(struct node);
	r->data = number;
	if(p==NULL || p->data > number)
	{
		p = r;
		p->next = temp;
	}
	while(temp != NULL)
	{
		if(temp->data<number && (temp->next==NULL || temp->next->data>number))
		{
			t2 = temp->next;
			temp->next = r;
			r->next = t2;
		}
		temp = temp->next;
	}
}


// Add a New Node to List-2
void add_list2(int number)
{
	struct node* temp = q, *r, *t2;
	r = (struct node*)new(struct node);
	r->data = number;
	if(q==NULL || q->data > number)
	{
		q = r;
		q->next = temp;
	}
	while(temp != NULL)
	{
		if(temp->data<number && (temp->next==NULL || temp->next->data>number))
		{
			t2 = temp->next;
			temp->next = r;
			r->next = t2;
		}
		temp = temp->next;
	}
}


/*
This function will merge the two given Linked Lists.
Rules of Mearging are - 
	>> No element will be repeated in the mearged Linked-List
	>> The merged list will be sorted in ascending order

Follows the simple algorithm to mearge two arrays.
*/
void merge_lists()
{
	if(p==NULL && q==NULL)
	{
		cout<<"Lists are Empty !!\n";
		return;
	}
	
	m = NULL;
	struct node *t1=p,*t2=q;
	struct node *z = NULL;
	
	while(t1!=NULL && t2!=NULL)
	{
		if(m == NULL)
		{
			m = (struct node*)new(struct node);
			z = m;
		}
		else
		{
			z->next = (struct node*)new(struct node);
			z = z->next;
		}
		
		if(t1->data < t2->data)
		{
			z->data = t1->data;
			t1 = t1->next;
		}
		else if(t1->data > t2->data)
		{
			z->data = t2->data;
			t2 = t2->next;
		}
		else if(t1->data == t2->data)
		{
			z->data = t1->data;
			t1 = t1->next ; t2 = t2->next;
		}
	}
	
	// if list-2 is smaller in size than list-1
	while(t1 != NULL)
	{
		if(z == NULL){ //if list_2 is entirely empty
			z = (struct node*)new(struct node);
			m = z;
		}
		else{
			z->next = (struct node*)new(struct node);
			z = z->next;
		}
		z->data = t1->data;
		t1 = t1->next;
	}
	
	// if list-1 is smaller in size than list-2
	while(t2 != NULL)
	{
		if(z == NULL){ //if list_1 is entirely empty
			z = (struct node*)new(struct node);
			m = z;
		}
		else{
			z->next = (struct node*)new(struct node);
			z = z->next;
		}
		z->data = t2->data;
		t2 = t2->next;
	}
	
	z->next = NULL; //last link of linked-list must be NULL
}


// Utility function to display List-1 or List-2
// Asks user to display which List (1 or 2)
void disp_list(int num)
{
	struct node* temp;
	
	if(num==1)		temp=p;
	else if(num==2)	temp=q;
	
	if(temp==NULL)
	{
		cout<<"List is Empty !!\n";
		return;
	}
	while(temp != NULL)
	{
		cout<<temp->data<<" ";
		temp = temp->next;
	}
	cout<<"\n";
}


// Utility function to display merged-list
void disp_merge_list()
{
	if(m == NULL)
	{
		cout<<"List is Empty !!\n";
		return;
	}
	struct node *temp = m;
	while(temp != NULL)
	{
		cout<<temp->data<<" ";
		temp = temp->next;
	}
	cout<<"\n";
}


// DRIVER CODE
int main()
{
	p=NULL ; q=NULL ; m=NULL;
	int optn, num;
	
	while(1)
	{
		cout<<"\nOpeartions available :\n";
		cout<<"1. Add node for list_1\n2. Add node for list_2\n";
		cout<<"3. Merge the two lists\n";
		cout<<"4. Display list\n5. Display merged list\n6. Exit\n\n";
		cout<<"Enter your choice : ";
		cin>>optn;
		
		switch(optn)
		{
			case(1):
				cout<<"Enter the number : ";
				cin>>num;
				add_list1(num);
				break;
			case(2):
				cout<<"Enter the number : ";
				cin>>num;
				add_list2(num);
				break;
			case(3):
				merge_lists();
				break;
			case(4):
				cout<<"Which list you want to see ?(1 or 2) : ";
				cin>>num;
				if(num==1 || num==2)	disp_list(num);
				else			cout<<"Invalid list number\n";
				break;
			case(5):
				disp_merge_list();
				break;
			case(6):
				exit(0);
		}
	}
	return 0;
}

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 1
Enter the number : 12

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 1
Enter the number : 13

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 2
Enter the number : -67

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 2
Enter the number : 56

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 4
Which list you want to see ?(1 or 2) : 1
12 13

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 4
Which list you want to see ?(1 or 2) : 2
-67 56

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 3

Opeartions available :
1. Add node for list_1
2. Add node for list_2
3. Merge the two lists
4. Display list
5. Display merged list
6. Exit

Enter your choice : 5
-67 12 13 56