AC212-计算两个递增有序单链表的并集，结果保存在 A 链表中，利用原有空间¶

代码实现¶

C
// 函数 Union：计算两个递增有序单链表的并集
// 将 A 和 B 中的所有元素合并并去重，结果保存在 A 链表中，利用原有空间
void Union(LinkList A, LinkList B) {
    LinkList ra = A, p = A->next, q = B->next; // 初始化指针
    B->next = NULL; // 断开 B 链表，防止后续操作影响 B 的结构

    // 循环条件：两个链表都还有未处理的节点
    while (p != NULL && q != NULL) {
        // 情况1：A 中当前元素小于 B 中当前元素
        if (p->data < q->data) {
            ra->next = p;    // 将较小元素连接到结果链表
            ra = p;          // 移动结果指针
            p = p->next;     // 移动 A 链表指针
        }
        // 情况2：A 中当前元素大于 B 中当前元素
        else if (p->data > q->data) {
            ra->next = q;    // 将较小元素连接到结果链表
            ra = q;          // 移动结果指针
            q = q->next;     // 移动 B 链表指针
        }
        // 情况3：A 中当前元素等于 B 中当前元素（重复元素）
        else {
            ra->next = p;    // 保留一个元素（选择 A 中的）
            ra = p;          // 移动结果指针
            p = p->next;     // 移动 A 链表指针

            LinkList r = q;  // r 指向 B 中的重复节点
            q = q->next;     // 移动 B 链表指针
            r->next = NULL;  // 断开被删除节点的链接
            free(r);         // 释放重复节点的内存
        }
    }

    // 处理剩余节点
    if (p != NULL) {
        ra->next = p; // 如果 A 还有剩余节点，全部连接到结果链表
    }
    if (q != NULL) {
        ra->next = q; // 如果 B 还有剩余节点，全部连接到结果链表
    }
}

代码逻辑解析¶

1. 初始化指针策略¶

ra = A：结果链表的尾指针，用于构建合并后的链表
p = A->next：指向 A 链表的第一个数据节点
q = B->next：指向 B 链表的第一个数据节点
B->next = NULL：断开 B 链表头部，确保后续操作的安全性

2. 三路比较逻辑¶

由于两个链表都是递增有序的，采用归并排序的思想：

情况1：p->data < q->data - A 中当前元素较小，将其加入结果链表 - 移动 A 链表指针，继续处理下一个元素

情况2：p->data > q->data - B 中当前元素较小，将其加入结果链表 - 移动 B 链表指针，继续处理下一个元素

情况3：p->data == q->data - 找到重复元素，只保留一个（选择 A 中的元素） - 删除 B 中的重复节点，释放内存

3. 剩余节点处理¶

由于两个链表都是有序的，剩余节点必然都大于已处理的所有元素
直接将剩余节点连接到结果链表末尾

时间复杂度分析¶

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

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

空间复杂度分析¶

额外空间使用：只使用了常量级别的额外变量（ra, p, q, r）
内存管理：重复节点及时释放，原有节点重新链接
空间利用：充分利用 A 和 B 的原有空间，不申请新的节点空间

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

较难理解部分的说明¶

为什么需要 `B->next = NULL`？¶

这行代码的作用是断开 B 链表的头部链接，防止在后续操作中意外修改 B 链表的结构。这是一个安全措施，确保： 1. 不会因为指针操作影响原始 B 链表的完整性 2. 避免可能出现的循环引用问题

为什么删除节点时需要 `r->next = NULL`？¶

C
LinkList r = q;
q = q->next;
r->next = NULL;  // 断开链接
free(r);

这一步是为了安全地释放内存： - 先保存要删除的节点指针 r - 移动 q 指针到下一个节点 - 断开被删除节点的所有链接 - 安全释放内存

图解说明¶

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

Text Only

初始状态：
ra -> A (结果链表头)
p -> 1 (A的第一个数据节点)
q -> 2 (B的第一个数据节点)

步骤1: p->data(1) < q->data(2)
- 选择 1，连接到结果链表
- 结果链表：A -> 1
- ra -> 1, p -> 3

步骤2: p->data(3) > q->data(2)
- 选择 2，连接到结果链表
- 结果链表：A -> 1 -> 2
- ra -> 2, q -> 3

步骤3: p->data(3) == q->data(3)
- 找到重复元素，选择 A 中的 3
- 删除 B 中的 3
- 结果链表：A -> 1 -> 2 -> 3
- ra -> 3, p -> 5, q -> 6

步骤4: p->data(5) < q->data(6)
- 选择 5，连接到结果链表
- 结果链表：A -> 1 -> 2 -> 3 -> 5
- ra -> 5, p -> 7

步骤5: p->data(7) > q->data(6)
- 选择 6，连接到结果链表
- 结果链表：A -> 1 -> 2 -> 3 -> 5 -> 6
- ra -> 6, q -> 8

步骤6: p->data(7) < q->data(8)
- 选择 7，连接到结果链表
- 结果链表：A -> 1 -> 2 -> 3 -> 5 -> 6 -> 7
- ra -> 7, p -> NULL

结束：p 为空，将 B 剩余节点连接
最终结果链表：A -> 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8 -> NULL

延伸知识点¶

1. 相关集合运算对比¶

C
// 交集 A∩B：保留两个链表中都存在的元素
void Intersection(LinkList A, LinkList B) {
    LinkList ra = A, p = A->next, q = B->next;
    B->next = NULL;

    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            LinkList temp = p;
            p = p->next;
            free(temp); // 删除 A 中的元素
        } else if (p->data > q->data) {
            LinkList temp = q;
            q = q->next;
            free(temp); // 删除 B 中的元素
        } else {
            ra->next = p; // 保留公共元素
            ra = p;
            p = p->next;
            q = q->next;
        }
    }
    // 释放剩余节点
    while (p != NULL) {
        LinkList temp = p;
        p = p->next;
        free(temp);
    }
    while (q != NULL) {
        LinkList temp = q;
        q = q->next;
        free(temp);
    }
    ra->next = NULL;
}

2. 双向链表版本¶

C
// 双向链表的并集操作
void UnionDoubly(DLinkList A, DLinkList B) {
    DLinkList ra = A, p = A->next, q = B->next;
    B->next = NULL;

    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            ra->next = p;
            p->prior = ra;  // 设置前驱指针
            ra = p;
            p = p->next;
        } else if (p->data > q->data) {
            ra->next = q;
            q->prior = ra;  // 设置前驱指针
            ra = q;
            q = q->next;
        } else {
            ra->next = p;
            p->prior = ra;  // 设置前驱指针
            ra = p;
            p = p->next;

            DLinkList r = q;
            q = q->next;
            r->next = NULL;
            free(r);
        }
    }

    if (p != NULL) {
        ra->next = p;
        p->prior = ra;
    }
    if (q != NULL) {
        ra->next = q;
        q->prior = ra;
    }
}

3. 带计数的并集操作¶

C
// 返回并集元素的个数
int UnionWithCount(LinkList A, LinkList B) {
    LinkList ra = A, p = A->next, q = B->next;
    B->next = NULL;
    int count = 0;

    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            ra->next = p;
            ra = p;
            p = p->next;
            count++;
        } else if (p->data > q->data) {
            ra->next = q;
            ra = q;
            q = q->next;
            count++;
        } else {
            ra->next = p;
            ra = p;
            p = p->next;
            LinkList r = q;
            q = q->next;
            free(r);
            count++; // 只计算一次重复元素
        }
    }

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

    ra->next = NULL;
    return count;
}

4. 数组版本的并集算法¶

C
// 对于数组的并集运算
void arrayUnion(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]) {
            result[k++] = B[j++];
        } else {
            result[k++] = A[i]; // 只保留一个
            i++;
            j++;
        }
    }

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

    *resultSize = k;
}

5. 实际应用场景¶

数据库合并：合并两个有序查询结果
搜索引擎：合并不同来源的排序结果
文件合并：合并两个有序文件
任务调度：合并有序的任务队列
社交网络：合并好友列表（去重）

这种方法充分利用了链表有序的特性，通过归并的思想实现了高效的集合并集运算，体现了算法设计中分治思想和空间复用的重要原则。