#include <iostream>
using namespace std;

class linklist
{
	private:
		struct node
		{
				int data;
				node *link;
		} *p;

	public:
		linklist();
		void addatend(int num);
		void addatbeg(int num);
		void addafter (int loc, int num);
		void display();
		int count();
		void add(int num);
		void del(int num);
		void merge (linklist &m, linklist &n);
		//void sort();
		void reverse();
		~linklist();
};

void linklist:: reverse()
{
	node *q, *r, *s;
	q=p;
	r=NULL;
	
	while(q!=NULL)
	{
		s=r;
		r=q;
		q=q->link;
		r->link=s;
	}
	
	p=r;
}

linklist:: linklist()
{
	p = NULL;
}

void linklist :: addatbeg(int num)
{
	node *temp;
	temp = new node;
	temp->data = num;
	temp->link=p;
	p=temp;
}

void linklist :: addatend(int num)
{
	struct node *temp, *r;
	if (p==NULL)
	{
		p = new node;
		p->data=num;
		p->link=NULL;
	}
	
	else
	{
		temp=p;
		
		while(temp->link != NULL)
		{
			temp=temp->link;
		}
		
		r =new node;
		r->data=num;
		r->link=NULL;
		temp->link=r;
	}
}

void linklist :: display()
{
	node *temp;
	temp = p;
	
	while (temp != NULL)
	{
		cout << endl;
		cout << temp->data;
		temp= temp->link;
	}
	
	cout << "Hello";
}

linklist :: ~linklist()
{
	node *temp, *r;
	r=p;
	while(temp!= NULL)
	{ 
		temp = r->link;
		delete r;
		r = temp;
	}
}	

void linklist :: addafter (int loc, int num)
{
	int cnt ;
	cnt = count();
	if ((loc < 1) || (loc > cnt ))
	{
		cout << "Input not valid ";
	}
	else
	{
		node *m=p;
		for (int i=1; i<loc; i++)
		{
			m = m->link;
		}
		
		node *temp;
		temp = new node;
		temp->data= num;
		temp->link=m->link;
		m->link=temp;
	}
}
	

int linklist :: count ()
{
	if (p==NULL)
	{
		return  0;
	}
	
	else
	{
		int count = 0;
		
		node *ct;
		ct = p;
		while(ct!=NULL)
		{
			count++;
			ct=ct->link;
		
		}
			
		return count;
	}
}
		
void linklist::add(int num) // add in ascending order
{
	node *r, *temp;
	r= new  node;
	r->data=num;
	temp=p;
	
	if (p==NULL || temp->data>num)
	{
		p=r;
		p->link=temp;
	}
	
	else
	{
		while(temp!=NULL)
		{
			if (temp->data <= num && ((temp->link==NULL)||(temp->link->data>num)))
			{
				r->link=temp->link;
				temp->link=r;
				return;
			}
			
			temp=temp->link;
		}		
	}
}
	
void linklist::merge(linklist &m, linklist &n)
{
    node *z;
    z=p;
    
    if(m.p==NULL && n.p==NULL) // if both list are empty
    return;
    
    while(m.p!=NULL && n.p!=NULL)
    {
        if(m.p->data>n.p->data)
        {
            z=new node;
            z->data=m.p->data;
            z->link=NULL;
            z=z->link;
            m.p=m.p->link;
        }
        
        else
        {
            if (m.p->data<n.p->data)
            {
                z=new node;
                z->data=n.p->data;
                z->link=NULL;
                z=z->link;
                n.p=n.p->link;
            }
            
            else 
            {
                z=new node;
                z->data=n.p->data;
                z->link=NULL;
                z=z->link;
                n.p=n.p->link;
                m.p=m.p->link;
            }
        }
    }
        
        while(m.p!=NULL)
        {
            z=new node;
            z->data=m.p->data;
            z->link=NULL;
            z=z->link;
            m.p=m.p->link;
        }
            
        while(n.p!=NULL)
        {
            z=new node;
            z->data=n.p->data;
            z->link=NULL;
            z=z->link;
            n.p=n.p->link;
        }
}
	
int main()
{

linklist m,n,l;

m.add(87);
m.add(82);
m.add(37);
m.add(47);
m.add(57);
m.add(77);
m.add(81);
m.display();

n.add(77);
n.add(93);
n.add(97);
n.add(33);
n.add(63);
n.add(73);
n.display();

l.merge(m,n);
l.display();
return 0;
}

if(m.p->data>n.p->data)
 {
    z=new node;
    z->data=m.p->data;
    z->link=NULL;
    z=z->link;
    m.p=m.p->link;
  }

/*
while both lists are not empty...
  {
    if the top of list1 is less than the top of list2...
      insert the value at the top of list1 into the union
    else if the top of list1 is less than the top of list2...
      insert the top of list2 into the union
    else
      insert the top of list1 into the intersection
  }
while list1 is not empty...
  insert the top of list1 into the union
while list2 is not empty...
  insert the top of list2 into the union
*/

// First find the nodes of each list.
// Create a list of data type;
I will use int, but you may use template.

int* pDataListA = new int[ElemntInListA];
int* pDataListB = new int[ElemntInListB];
int* pResultList = new int[ElemntInListA + ElemntInListB];


Node* pANode = HeadOfLinkListA;
int Index = 0;
while (pANode != NULL)
{
	pDataListA[Index] = 	pANode->data;
Index++;
pANode = pANode->link;
}

Node* pBNode = HeadOfLinkListB;
Index = 0;
while (pBNode!= NULL)
{
	pDataListB[Index] = 	pBNode ->data;
Index++;
pBNode = pBNode ->link;
}

MergeSort(pDataListA, pDataListB, pResultList);

Create a new linklist and use your add Function with pResultList.
delete pDataListA ;
delete pDataListB;
delete pDataListC;

MergeSort(int* pArrayA, int SizeA, int* pArrayB, int SizeB, int* pArrayC)
{
int aDex = 0;
int bDex = 0;
int cDes = 0;
while ( aDex < SizeA && bDex < SizeB)
pArrayC[cDex++] =  (pArrayA[aDex] < pArrayB[bDex]) ? pArrayA[aDex++] :
 pArrayB[BDex++]
while (aDex < SizeA)
pArrayC[cDex++] =   pArrayA[aDex++] :

while (bDex < SizeB)
pArrayC[cDex++] =   pArrayB[bDex++] :
}