（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

（4）已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

[题目分析]
求两个集合A和B的差集是指在A中删除A和B*有的元素，即删除链表中的相应结点,所以要保存待删除结点的前驱，使用指针pre指向前驱结点。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点，从第一个结点开始进行比较，当两个链表La和Lb均为到达表尾结点时，如果La表中的元素小于Lb表中的元素，pre置为La表的工作指针pa删除Lb表中的元素；如果其中一个表中的元素较小时，删除此表中较小的元素，此表的工作指针后移。当链表La和Lb有一个为空时，依次删除另一个非空表中的所有元素。

#include <iostream>
using namespace std;
//定义存储
typedef struct LNode
{
    int date;
    struct LNode *next;
} Lnode, *Linklist;

//链表初始化
void init(Linklist &L)
{
    L = new Lnode;  // 开辟空间
    L->next = NULL; //头节点置为空
}
//输出数据
void output(Linklist &T)
{
    Linklist p = T;
    p = p->next;
    while (p)
    {
        cout << p->date;
        p = p->next;
    }
}
//后插法构建链表
void CreateLiklist(Linklist &L, int n)
{
    Linklist r = L;
    for (int i = 0; i < n; i++)
    {
        Linklist p = new Lnode; //开辟空间，p为节点
        printf("请输入%d个数据\n", i + 1);
        cin >> p->date;
        p->next = NULL;
        r->next = p; //将新节点插入r之后
        r = p;       ////r指向新的尾节点
    }
}
void Difference(Linklist &La, Linklist &Lb, int &n)
{
    Linklist pa = La->next;
    Linklist pb = Lb->next;
    Linklist pre = La;
    while (pa && pb)
    {
        if (pa->date < pb->date)
        {
            pre = pa;
            pa = pa->next;
            n++;
        }
        else if (pa->date > pb->date)
        {
            pb = pb->next;
        }
        else
        {
            pre->next = pa->next;
            Linklist u = pre;
            pa = pa->next;
            delete u;
        }
    }
}
int main()
{
    Linklist La, Lb, Lc;
    //初始化
    init(La);
    init(Lb);
    int n1, n2;
    cout << "请输入请输入每条链表的个数" << endl;
    scanf("%d %d", &n1, &n2);
    int n;

    //构建链表
    CreateLiklist(La, n1);
    CreateLiklist(Lb, n2);
    Difference(La, Lb, n);
    output(La);
}