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

typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

void CreateLinkList(LinkList &L,int n){             //尾插法建立单向链表,头结点不用

    LinkList cur,pNew;
    int i,x;
    L=cur=NULL;
    for(i=0;i<=n;i++){
        pNew=(LinkList)malloc(sizeof(LNode));
        cin>>x;
        pNew->data=x;
        if(i==0){
            L=cur=pNew;
            L->data=-1;
        }
        else{
            cur->next=pNew;
            cur=pNew;
        }
    }
    cur->next=NULL;

}

int QuickSort(LinkList &L,LinkList tail){
    LinkList mid,p,q,m;
    int key;
   
    if (L->next==tail || L->next->next==tail)
        return -1;

    mid=L->next;
    p=L;
    q=mid;
    key=mid->data;
    m=mid->next;
   
    while (m!=tail){
        if (m->data<key)
            p=p->next=m;
        else
            q=q->next=m;
        m=m->next;
    }

    p->next = mid;
    q->next = tail;

    QuickSort(L,mid);
    QuickSort(mid,tail);

    return 0;
}

void Print(LinkList L){
    LinkList p;
    p=L->next;
    cout<<"{";
    while(p){
        cout<<p->data;
        if(p->next!=NULL)
            cout<<",";
        p=p->next;
    }
    cout<<"}"<<endl;

}

void AddList(LinkList La,LinkList Lb){
    LinkList Lc;
    LinkList cur,la,lb,ln;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;

    while(la && lb){
        if(la->data<lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
        }
        else if(la->data==lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
            lb=lb->next;
        }
        else{
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=lb->data;
            cur->next=ln;
            cur=ln;
            lb=lb->next;
        }
    }
    while(la){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=la->data;
        cur->next=ln;
        cur=ln;
        la=la->next;
    }
    while(lb){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=lb->data;
        cur->next=ln;
        cur=ln;
        lb=lb->next;
    }
    cur->next=NULL;
   
    Print(Lc);
}

void JiaoList(LinkList La,LinkList Lb){
    LinkList Lc,la,lb,ln,cur;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;
    while(la && lb){
        if(la->data<lb->data)
            la=la->next;
        else if(la->data==lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
            lb=lb->next;
        }
        else
            lb=lb->next;
    }
        cur->next=NULL;
        Print(Lc);
}

void ChaList(LinkList La,LinkList Lb){
    LinkList Lc,la,lb,cur,ln;

    Lc=cur=(LinkList)malloc(sizeof(LNode));
    la=La->next;
    lb=Lb->next;
   
    while(la && lb){
        if(la->data<lb->data){
            ln=(LinkList)malloc(sizeof(LNode));
            ln->data=la->data;
            cur->next=ln;
            cur=ln;
            la=la->next;
        }
        else if(la->data==lb->data){
            la=la->next;
            lb=lb->next;
        }
        else
            lb=lb->next;
    }
    while(la){
        ln=(LinkList)malloc(sizeof(LNode));
        ln->data=la->data;
        cur->next=ln;
        cur=ln;
        la=la->next;
    }
    cur->next=NULL;
    Print(Lc);
}

int main(){
    LinkList La,Lb;
    int na,nb;
    cout<<"请输入第一个集合的元素数目:"<<endl;
    cin>>na;
    cout<<"请输入集合元素<头结点不用!>"<<endl;
    CreateLinkList(La,na);
    cout<<"请输入第二个集合的元素数目:"<<endl;
    cin>>nb;
    cout<<"请输入集合元素<头结点不用!>"<<endl;
    CreateLinkList(Lb,nb);
    QuickSort(La,NULL);
    QuickSort(Lb,NULL);
    cout<<"集合LA:";
    Print(La);
    cout<<"集合LB:";
    Print(Lb);
    cout<<"LA和LB的并集为:";
    AddList(La,Lb);
    cout<<"LA和LB的交集为:";
    JiaoList(La,Lb);
    cout<<"LA和LB的差集为:";
    ChaList(La,Lb);

    return 0;
}