AC211-计算两个递增有序单链表的差集 A-B，且要求利用 A 的原有空间¶

代码实现¶

C
// 函数 Diff：计算两个递增有序单链表的差集 A-B
// 从 A 中删除那些在 B 中也存在的元素，结果仍保存在 A 链表中
void Diff(LinkList A, LinkList B) {
    LinkList p = A, q = B->next; // p 指向 A 链表的头节点，q 指向 B 链表的第一个数据节点

    // 循环条件：p 的后继节点不为空 且 q 节点不为空
    while (p->next != NULL && q != NULL) {
        // 情况1：A 中当前元素大于 B 中当前元素
        if (p->next->data > q->data) {
            q = q->next; // B 中的元素较小，移动 q 指针寻找更大的元素
        }
        // 情况2：A 中当前元素小于 B 中当前元素
        else if (p->next->data < q->data) {
            p = p->next; // A 中的元素较小，该元素属于差集，保留并移动 p 指针
        }
        // 情况3：A 中当前元素等于 B 中当前元素
        else {
            // 找到公共元素，需要从 A 中删除该元素
            LinkList r = p->next;        // r 指向要删除的节点
            p->next = r->next;           // 将 p 的 next 指向被删除节点的后继
            free(r);                     // 释放被删除节点的内存
            q = q->next;                 // 移动 q 指针到下一个节点
            // 注意：p 指针不移动，因为删除后 p->next 已经改变
        }
    }
    // 循环结束后，A 中剩余的所有元素都属于差集 A-B，无需额外处理
}

代码逻辑解析¶

1. 初始化指针策略¶

p = A：p 指向链表 A 的头节点，通过 p->next 访问数据节点
q = B->next：q 直接指向链表 B 的第一个数据节点
这种策略便于删除操作和遍历

2. 三路比较逻辑¶

由于两个链表都是递增有序的，可以利用这一特性进行高效的比较：

情况1：p->next->data > q->data - A 中当前元素大于 B 中当前元素 - 说明 B 中可能存在与 A 当前元素相等的更大元素 - 移动 q 指针继续寻找

情况2：p->next->data < q->data - A 中当前元素小于 B 中当前元素 - 由于 B 是递增的，B 后面不可能有与 A 当前元素相等的元素 - 说明 A 当前元素属于差集 A-B，保留该元素 - 移动 p 指针继续处理下一个元素

情况3：p->next->data == q->data - 找到公共元素 - 从 A 中删除该元素（因为要求 A-B） - 同时移动两个指针

3. 循环终止后的处理¶

循环结束后： - 如果是 q 先为空：A 中剩余的所有元素都不在 B 中，都属于差集 - 如果是 p->next 先为空：A 中所有元素都已处理完毕 - 两种情况都不需要额外处理

时间复杂度分析¶

循环次数：每次循环至少移动一个指针
指针移动：
p 指针最多移动 m 次（m 为 A 链表长度）
q 指针最多移动 n 次（n 为 B 链表长度）
操作复杂度：每次操作都是 O(1)

因此，时间复杂度为 O(m + n)

空间复杂度分析¶

额外空间使用：只使用了常量级别的额外变量（p, q, r）
内存管理：删除的节点及时释放，没有内存泄漏

因此，空间复杂度为 O(1)

较难理解部分的说明¶

为什么删除节点后 p 指针不移动？¶

C
// 删除操作后的情况
原状态: ... -> p -> 要删除节点 -> next节点 -> ...
删除后: ... -> p -> next节点 -> ...

删除节点后，p->next 已经指向了新的节点，如果此时移动 p 指针，就会跳过对新节点的检查。因此需要保持 p 不动，继续检查新连接的节点。

图解说明¶

假设： - A 链表：A -> 1 -> 3 -> 5 -> 7 -> 9 -> NULL - B 链表：B -> 2 -> 3 -> 6 -> 7 -> NULL

Text Only

初始状态：
p -> A (头节点)
q -> 2 (B的第一个数据节点)

步骤1: p->next->data(1) < q->data(2)
- 1 属于差集，保留
- p 移动到节点 1

步骤2: p->next->data(3) > q->data(2)  
- q 移动到节点 3

步骤3: p->next->data(3) == q->data(3)
- 找到公共元素 3，删除 A 中的 3
- p 不移动，q 移动到节点 6

步骤4: p->next->data(5) < q->data(6)
- 5 属于差集，保留
- p 移动到节点 5

步骤5: p->next->data(7) == q->data(7)
- 找到公共元素 7，删除 A 中的 7
- p 不移动，q 移动到 NULL

结束：q 为空，循环结束
最终 A 链表：A -> 1 -> 5 -> 9 -> NULL

延伸知识点¶

1. 相关集合运算¶

C
// 并集 A∪B：将两个链表合并为一个有序链表
void Union(LinkList A, LinkList B) { /* 实现略 */ }

// 交集 A∩B：保留两个链表中都存在的元素
void Intersection(LinkList A, LinkList B) { /* 实现略 */ }

// 对称差集 (A-B)∪(B-A)：保留只在一个链表中出现的元素
void SymmetricDiff(LinkList A, LinkList B) { /* 实现略 */ }

2. 优化版本 - 带返回值¶

C
// 返回差集中元素的个数
int DiffWithCount(LinkList A, LinkList B) {
    LinkList p = A, q = B->next;
    int count = 0;

    while (p->next != NULL && q != NULL) {
        if (p->next->data > q->data) {
            q = q->next;
        } else if (p->next->data < q->data) {
            p = p->next;
            count++;
        } else {
            LinkList r = p->next;
            p->next = r->next;
            free(r);
            q = q->next;
        }
    }

    // 计算剩余节点数
    LinkList temp = p->next;
    while (temp != NULL) {
        count++;
        temp = temp->next;
    }

    return count;
}

3. 数组版本的差集算法¶

C
// 对于数组的差集运算
void arrayDiff(int A[], int m, int B[], int n, int result[], int* resultSize) {
    int i = 0, j = 0, k = 0;

    while (i < m && j < n) {
        if (A[i] < B[j]) {
            result[k++] = A[i++];
        } else if (A[i] > B[j]) {
            j++;
        } else {
            i++; // 跳过相同元素
            j++;
        }
    }

    // 复制 A 中剩余的元素
    while (i < m) {
        result[k++] = A[i++];
    }

    *resultSize = k;
}

4. 实际应用场景¶

数据库查询：实现 SQL 中的 NOT IN 操作
文件系统：找出在目录 A 中但不在目录 B 中的文件
权限管理：计算用户权限的差集
数据同步：找出需要同步的数据项

这种方法充分利用了链表有序的特性，通过双指针技术实现了高效的集合差集运算，体现了算法设计中利用数据特性优化算法的重要思想。

AC211-计算两个递增有序单链表的差集 A-B，且要求 利用 A 的原有空间¶