#include <iostream.h>
#include <stdlib.h>

typedef int datatype;
struct LNode//結構定義
{datatype data;
 struct LNode *next;
};

void InitList (LNode *  HL)//初始化
{
	HL->next=NULL;
}


void TraverseList(LNode *  HL)//遍歷線性表
{
    LNode *p=HL->next;
    while(p!=NULL) {
	    cout << p->data <<" ";
        p=p->next;
    }
    cout<<endl;
}


void InsertRear(LNode *  HL, datatype item)//表尾插入
{
	LNode *newptr;
    newptr=new LNode;//為保存新元素動態分配結點,newptr指向該結點
    if(newptr==NULL)//未分配到結點
    {
		cerr<<"Memory allocation failare !"<<endl;
        exit(1);
    }
    newptr->data=item;//給新結點值域賦值
    newptr->next=NULL;//給新結點指針域賦值
    
		LNode * p=HL;
        while(p->next!= NULL)//從表頭遍歷,p指向表尾元素
			p=p->next;
            p->next=newptr;//將新結點鏈接到表尾
	
}


void Mergelist(LNode *La,LNode *Lb,LNode *&Lc)//將兩個有序鏈表并為一個有序鏈表,"*&Lc"為指針的引用
{ 
	LNode *Pa,*Pb,*Pc;	
    Pa=La->next;Pb=Lb->next;
	Lc=La;Pc=Lc;
	while(Pa!=NULL&&Pb!=NULL)
	{
		if(Pa->data<=Pb->data)
		{
			Pc->next=Pa;Pc=Pa;Pa=Pa->next;
		}
		else
		{
			Pc->next=Pb;Pc=Pb;Pb=Pb->next;
		}		
    }
	if(Pa!=NULL)
		Pc->next=Pa;
	else
		Pc->next =Pb;
	delete Lb;
}

void main()//主程序
{
	LNode *La,*Lb,*Lc;
	La=new LNode;
	Lb=new LNode;
	Lc=new LNode;
    InitList(La);
    InitList(Lb);
    InitList(Lc);
    int n,i,j,x,m,y;
    cout<<"輸入La的元素個數";
    cin>>n;
    cout<<"輸入La的元素";
    for(i=1;i<=n;i++)
       {
        cin>>x;
        InsertRear(La,x);
       }
	TraverseList(La);
    cout<<endl;
    cout<<"輸入Lb的元素個數:";
    cin>>m;
    cout<<"輸入Lb的元素:";
    for(j=1;j<=m;j++)
       {
        cin>>y;
        InsertRear(Lb,y);
       }
	TraverseList(Lb);
	cout<<endl;

Mergelist(La,Lb,Lc);//調用函數Mergelist

TraverseList(Lc);//遍歷新的單鏈表
}