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

以下是算法的实现：

int getDifference(int *A, int lenA, int *B, int lenB, int *C) {
    int i = 0, j = 0, k = 0;
    while (i < lenA && j < lenB) {
        if (A[i] < B[j]) {
            C[k++] = A[i++];
        } else if (A[i] > B[j]) {
            j++;
        } else {
            i++;
            j++;
        }
    }
    while (i < lenA) {
        C[k++] = A[i++];
    }
    return k;
}

其中，A 和 B 分别表示两个集合，C 表示它们的差集，lenA 和 lenB 分别表示 A 和 B 的长度。算法的思路是，使用两个指针 i 和 j 分别指向 A 和 B 的开头，然后比较它们的元素大小，如果 A[i] < B[j]，则将 A[i] 加入到 C 中，然后 i++；如果 A[i] > B[j]，则将 j++，表示 B 中没有 A[i] 这个元素；如果 A[i] == B[j]，则表示 A 和 B 中都有这个元素，所以 i++ 和 j++。最后，如果 A 中还有剩余的元素，就将它们全部加入到 C 中。最后返回 C 的长度，即为差集的元素个数。

相关问题

已知两个链表A和B分别表示两个集合，其元素递增排列。请设计算法求出两个集合A和B 的差集C

1. 初始化三个指针，分别指向链表A、B和C的头结点。
2. 遍历链表A和B，比较当前节点的值，如果A的值小于B的值，则将A的节点加入到C中，A指针后移；如果B的值小于A的值，则将B的节点丢弃，B指针后移；如果A和B的值相等，则丢弃两个节点，A和B指针同时后移。
3. 如果遍历完链表A后B还有剩余节点，将剩余节点加入到C中。
4. 返回链表C的头结点。

代码实现：

ListNode* getDifference(ListNode* A, ListNode* B) {
    ListNode* C = new ListNode(0);
    ListNode* pA = A;
    ListNode* pB = B;
    ListNode* pC = C;
    while (pA != NULL && pB != NULL) {
        if (pA->val < pB->val) {
            pC->next = new ListNode(pA->val);
            pA = pA->next;
            pC = pC->next;
        } else if (pA->val > pB->val) {
            pB = pB->next;
        } else {
            pA = pA->next;
            pB = pB->next;
        }
    }
    while (pB != NULL) {
        pB = pB->next;
    }
    return C->next;
}

已知两个链表A和B分别表示两个集合，其元素递增排列，请设计算法求出A与B的交集，并存放于A链表中

1. 定义两个指针pA和pB分别指向链表A和链表B的头节点。
2. 遍历两个链表，比较pA和pB指向的节点的值，如果相等，则将该节点加入结果链表中，并将pA和pB都指向下一个节点；如果pA指向的节点的值小于pB指向的节点的值，则将pA指向下一个节点；反之，将pB指向下一个节点。
3. 当其中一个链表遍历完毕时，结束循环。
4. 将结果链表中的元素复制到链表A中。
5. 返回链表A作为交集。

代码实现：

void intersection(ListNode* A, ListNode* B){
    ListNode* pA = A->next;
    ListNode* pB = B->next;
    ListNode* result = new ListNode(0);
    ListNode* p = result;
    while(pA != nullptr && pB != nullptr){
        if(pA->val == pB->val){
            p->next = pA;
            p = p->next;
            pA = pA->next;
            pB = pB->next;
        }else if(pA->val < pB->val){
            pA = pA->next;
        }else{
            pB = pB->next;
        }
    }
    p->next = nullptr;
    A->next = result->next;
}