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

### 回答1：
该题目涉及到集合的元素递增排列问题。假设已知集合A和B分别表示两个集合，并且集合A中的元素递增排序。请设计算法求出两个集合A和B的差集（即仅包含在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。

### 回答2：
解题思路：

为了求出集合a和集合b的差集，我们可以从头到尾依次扫描这两个链表，每遇到一个不同的元素，就将其加入新的链表res中。

具体实现：

- 定义链表节点结构体

struct ListNode {
    int val;
    struct ListNode *next;
};

- 定义函数进行差集运算

int getDifference(struct ListNode* a, struct ListNode* b, struct ListNode* res) {
    int count = 0; // 记录差集元素个数
    struct ListNode* p = a;
    struct ListNode* q = b;
    struct ListNode* r = res;
    while (p != NULL && q != NULL) { // 遍历a和b链表
        if (p->val < q->val) { // 如果a链表当前节点的值小于b链表当前节点的值，将a链表当前节点的值加入差集
            count++;
            r->next = (struct ListNode*)malloc(sizeof(struct ListNode));
            r = r->next;
            r->val = p->val;
            p = p->next;
        } else if (p->val > q->val) { // 如果a链表当前节点的值大于b链表当前节点的值，继续遍历b链表
            q = q->next;
        } else { // 如果a链表当前节点的值等于b链表当前节点的值，继续遍历a和b链表
            p = p->next;
            q = q->next;
        }
    }
    while (p != NULL) { // 遍历a链表剩余部分，将剩余节点加入差集
        count++;
        r->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        r = r->next;
        r->val = p->val;
        p = p->next;
    }
    r->next = NULL; // 将res链表最后一个节点的next赋为NULL
    return count;
}

- 测试

int main() {
    // 初始化链表a
    struct ListNode *a = (struct ListNode *)malloc(sizeof(struct ListNode));
    a->val = 1;
    a->next = (struct ListNode *)malloc(sizeof(struct ListNode));
    a->next->val = 3;
    a->next->next = (struct ListNode *)malloc(sizeof(struct ListNode));
    a->next->next->val = 5;
    a->next->next->next = NULL;
    // 初始化链表b
    struct ListNode *b = (struct ListNode *)malloc(sizeof(struct ListNode));
    b->val = 2;
    b->next = (struct ListNode *)malloc(sizeof(struct ListNode));
    b->next->val = 4;
    b->next->next = NULL;
    // 初始化差集链表res
    struct ListNode *res = (struct ListNode *)malloc(sizeof(struct ListNode));
    res->next = NULL;
    // 求a和b的差集
    int count = getDifference(a, b, res);
    // 输出差集元素个数
    printf("差集元素个数为%d\n", count);
    // 输出差集链表
    printf("差集链表为:");
    struct ListNode *r = res->next;
    while (r != NULL) {
        printf("%d ", r->val);
        r = r->next;
    }
    printf("\n");
    return 0;
}

输出结果如下：

差集元素个数为2
差集链表为:1 5

算法时间复杂度：O(max(m,n))，其中m和n分别为链表a和链表b的长度。

### 回答3：
题目要求求出链表a和链表b的差集，即在链表a中出现但不在链表b中出现的元素所构成的集合。因此我们需要遍历链表a和链表b，找到a中不在b中的元素。

算法思路：

1. 声明一个变量count来记录差集中元素的个数，初始化为0。
2. 分别遍历链表a和链表b，将它们的元素值进行比较。
3. 若当前a链表的元素值小于b链表的元素值，则将a链表往后移一位。
4. 若当前a链表的元素值大于b链表的元素值，则将b链表往后移一位。
5. 若当前a链表的元素值等于b链表的元素值，则同时将a和b链表往后移一位。
6. 若当前a链表的元素值不等于b链表的元素值，则将a的元素值打印出来，同时将a链表往后移一位。
7. 继续执行步骤2~6，直到链表a和链表b都为空。
8. 返回元素个数count。

算法实现：

int get_difference(ListNode* a, ListNode* b)
{
    int count = 0;
    ListNode* pa = a;
    ListNode* pb = b;

    while (pa != NULL && pb != NULL) {
        if (pa->val < pb->val)
            pa = pa->next;
        else if (pa->val > pb->val)
            pb = pb->next;
        else {
            pa = pa->next;
            pb = pb->next;
        }
        if (pa != NULL && pb != NULL && pa->val != pb->val) {
            count++;
            cout << pa->val << " ";
            pa = pa->next;
        }
    }

    return count;
}

此算法的时间复杂度为O(max(m,n))，其中m和n分别为链表a和链表b的长度。