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

### 回答1：
算法思路：

1. 定义两个指针p和q分别指向链表a和b的头结点；
2. 定义一个新链表c，用于存储a中不在b中出现的元素；
3. 当p和q都不为空时，比较p和q所指向的元素大小，如果p所指向的元素小于q所指向的元素，则将p所指向的元素插入到链表c中，并将p指向下一个元素；如果p所指向的元素大于q所指向的元素，则将q指向下一个元素；
4. 如果p不为空而q为空，则将p所指向的元素插入到链表c中，并将p指向下一个元素；
5. 最后返回链表c的元素个数。

算法实现：

int difference(Node* a, Node* b, Node*& c) {
    int count = 0;
    Node* p = a;
    Node* q = b;
    Node* tail = nullptr;
    c = nullptr;
    while (p != nullptr && q != nullptr) {
        if (p->data < q->data) {
            Node* node = new Node(p->data);
            if (c == nullptr) {
                c = node;
                tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
            count++;
            p = p->next;
        } else if (p->data > q->data) {
            q = q->next;
        } else {
            p = p->next;
            q = q->next;
        }
    }
    while (p != nullptr) {
        Node* node = new Node(p->data);
        if (c == nullptr) {
            c = node;
            tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        count++;
        p = p->next;
    }
    return count;
}

其中，Node为链表节点的结构体，包含一个整型数据data和一个指向下一个节点的指针next。函数difference的参数a和b分别为链表a和b的头结点，参数c为返回的差集链表的头结点的指针。函数返回差集链表的元素个数。

### 回答2：
首先，我们可以从头到尾遍历两个链表，将a链表中但不在b链表中的元素添加到一个新的结果链表中。这个思路已经很明显地实现了集合的求差，但是如何避免在插入新节点时对结果链表进行遍历呢？

我们可以构建一个虚拟头节点，将其指向结果链表的第一个元素。在遍历a和b链表时，若当前a链表节点的元素值小于b链表节点的元素值，则把a链表节点添加到结果链表中。若相等，则a链表和b链表节点同时后移。若a链表节点的元素值大于b链表节点的元素值，则直接将b链表节点后移。如此循环遍历两个链表，直到任意一个链表遍历结束，最后剩下的a链表中的元素就是a集合中不在b集合中的元素。

以下是具体的代码实现：

Node* getDifferenceSet(Node* a, Node* b, int& count) {
Node* dummyHead = new Node(-1); // 构建虚拟头节点
Node* tail = dummyHead; // 记录结果链表的尾部
count = 0; // 统计结果链表的元素个数

while (a != nullptr && b != nullptr) {
if (a->val < b->val) { // a链表中的元素不在b链表中
tail->next = new Node(a->val);
tail = tail->next;
count++;
a = a->next;
} else if (a->val == b->val) { // a链表和b链表中的元素相等
a = a->next;
b = b->next;
} else { // a链表中的元素已经不可能在b链表中
b = b->next;
}
}

while (a != nullptr) { // 将a链表中剩下的元素添加到结果链表中
tail->next = new Node(a->val);
tail = tail->next;
count++;
a = a->next;
}

return dummyHead->next;
}

其中，参数count是传引用的，返回结果链表时同时更新了元素个数。总时间复杂度为O(N)，其中N是两个链表的节点数之和，空间复杂度为O(N)。

### 回答3：
首先，我们需要明确什么是差集。差集指的是仅由一个集合中出现而另一个集合中不出现的元素所构成的集合。因此，我们需要遍历链表a和链表b，将仅在链表a中出现的元素加入差集中。为了方便存储，我们可以通过链表来构建差集。具体算法如下：

1. 初始化指针p和q分别指向链表a和链表b的头节点。
2. 初始化一个空的链表，用于存储差集。
3. 循环遍历链表a和链表b，如果p所指向的节点的值小于q所指向的节点的值，则将p所指向的节点的值添加到差集中，并将p指向下一个节点；否则，将q指向下一个节点。
4. 如果p已经到达链表a的尾部，将链表b中剩余的元素全部加入差集中。
5. 返回差集的元素个数。

代码实现如下：

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

int getDifference(ListNode* a, ListNode* b, ListNode* &c) {
    c = new ListNode(0); // 初始化差集链表
    ListNode* p = a;
    ListNode* q = b;
    ListNode* cur = c;
    int count = 0; // 差集元素个数
    while (p && q) {
        if (p->val < q->val) { // a中元素小于b中元素，加入差集
            cur->next = new ListNode(p->val);
            cur = cur->next;
            p = p->next;
            count++;
        } else if (p->val > q->val) { // b中元素小于a中元素，移动指针q
            q = q->next;
        } else { // a和b中元素相等，都移动指针
            p = p->next;
            q = q->next;
        }
    }
    // 将b中剩余元素加入差集
    while (p) {
        cur->next = new ListNode(p->val);
        cur = cur->next;
        p = p->next;
        count++;
    }
    c = c->next;
    return count;
}

其中，c是差集链表的头节点。最后记得要删除头节点，将需要的差集链表返回。时间复杂度为O(m+n)，m和n分别是链表a和链表b的长度。