#include<iostream>
#include<cstdlib>
using namespace std;

#define OK 1;
#define ERROR 0;
typedef int Status;
typedef int DataType;
typedef struct LNode//Linked list=链表
{
    DataType data;
    struct LNode *next;
}LNode,*LinkList;

Status InitLink(LinkList &L)
{
    L=new(LNode);
    L->next=NULL;
    if(!L)
        return ERROR;//生成失败
    return OK;
}

Status InsertLink(LinkList &L,DataType e,int n)//在第i个元素之前插入
{//设计为有头结点
    int j=0;//刚开始，p指向头结点，所以j=0
    LNode *p,*s;//一个p拿来指向要插入的结点的前一个结点，s用来生成新的结点
    p=L;
    while(p&&j<n-1)
    {
        p=p->next;
        j++;
    }
    if(!p||j>n-1)
        return ERROR;
    s=new(LNode);
    s->data=e;
    s->next=p->next;
    p->next=s;
    return OK;
}

void CreateLink(LinkList &L)
{
    int a,i;
    DataType b;
    cout<<"输入这个链表的元素个数：";
    cin>>a;
    cout<<"输入这个链表的数据：";
    for(i=1;i<=a;i++)//在第一个元素之前插入数据，插入的就是第一个元素了
    {
        cin>>b;
        InsertLink(L,b,i);
    }
}

void Print(LinkList L)
{
    int i;
    LNode *p;
    p=L->next;
    while(p)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}
void Map(LinkList L1,LinkList L2,LinkList &Lc)
{
    LNode *pa=L1->next,*pb=L2->next;
    Lc=L1;
    LNode *pc=Lc;
    while(pa&&pb)
        if(pa->data<pb->data)
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
        }
        else if(pa->data>pb->data)
        {
            pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
        else
        {
            pc->next=pa;
            pc=pa;
            pa=pa->next;
            pb=pb->next;
        }
    if(pa)
        pc->next=pa;
    else pc->next=pb;

}
int main(void)
{
    LinkList L1,L2,Lc;
    if(!InitLink(L1))
    {
        cout<<"生成失败";
        exit(1);
    }

    CreateLink(L1);
    InitLink(L2);
    CreateLink(L2);
    cout<<"第一个链表为：";
    Print(L1);
    cout<<"第二个链表为：";
    Print(L2);
    cout<<"合并后为：";
    Map(L1,L2,Lc);
    Print(Lc);

}