208MergeList

//mergeList.cpp
#include"C:\Users\Administrator\Documents\Visual Studio 2013\Projects\204LinkList\204LinkList\c1.h"
#include"C:\Users\Administrator\Documents\Visual Studio 2013\Projects\204LinkList\204LinkList\elemtype.h"
#include"C:\Users\Administrator\Documents\Visual Studio 2013\Projects\204LinkList\204LinkList\c2-2.h"
#include"C:\Users\Administrator\Documents\Visual Studio 2013\Projects\204LinkList\204LinkList\bo2-2.cpp"
#include"C:\Users\Administrator\Documents\Visual Studio 2013\Projects\204LinkList\204LinkList\function.h"

//insert elements into head
void CreateHeadList(LinkList &L, int n)
{
	LinkList p;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = nullptr;
	for (int i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(LNode));
		cin >> p->data;
		p->next = L->next;
		L->next = p;
	}
}

//insert elements into tail
void CreateTailList(LinkList &L, int n)
{
	LinkList p, q;
	L = (LinkList)malloc(sizeof(LNode));
	q = L;
	for (int i = 0; i < n; i++)
	{
		p = (LinkList)malloc(sizeof(LNode));
		cin >> p->data;
		q->next = p;
		q = q->next;
	}
	q->next = nullptr;	
}

void MergeList(LinkList La, LinkList &Lb, LinkList &Lc)
{
	LinkList pa = La->next, pb = Lb->next, pc;
	Lc = pc = La;
	while (pa && pb)
	{
		if (pa->data <= pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;
	free(Lb);
	Lb = La = nullptr;
}

int main()
{
	int n = 5;
	LinkList La, Lb, Lc;

    cout << "head insert" << endl;
	CreateHeadList(La, n);
	ListTraverse(La, print);
	cout << endl;

    cout << "tail insert" << endl;
	CreateTailList(Lb, n);
	ListTraverse(Lb, print);
	cout << endl;
	MergeList(La, Lb, Lc);
	ListTraverse(Lc, print);
	cout << endl;
	
	cin.get();
	cin.get();
	return 0;
}