AC209-找出两个递增有序单链表的公共元素，构建新的链表 C，要求不破坏 A 和 B 中的结点¶

代码实现¶

C
// 函数 common：找出两个递增有序单链表的公共元素，构建新的链表 C
// 参数：A 和 B 是两个递增有序的单链表
// 返回值：包含公共元素的新链表 C
LinkList common(LinkList A, LinkList B) {
    // 创建新链表 C 的头节点
    LinkList C = (LinkList)malloc(sizeof(LNode));
    LinkList p = A->next, q = B->next, rc = C; // p、q 分别指向 A、B 的第一个数据节点，rc 指向 C 的尾节点

    // 当两个链表都未遍历完时继续循环
    while (p != NULL && q != NULL) {
        // 如果 A 当前节点的值大于 B 当前节点的值
        if (p->data > q->data) {
            q = q->next; // 移动 B 的指针，寻找更大的值
        }
        // 如果 A 当前节点的值小于 B 当前节点的值
        else if (p->data < q->data) {
            p = p->next; // 移动 A 的指针，寻找更大的值
        }
        // 如果两个节点的值相等（找到公共元素）
        else {
            // 创建新节点存储公共元素
            LinkList r = (LinkList)malloc(sizeof(LNode));
            r->data = p->data; // 将公共元素值复制到新节点

            // 将新节点链接到链表 C 的末尾
            rc->next = r;
            rc = r; // 更新 C 的尾指针

            // 同时移动两个链表的指针，继续寻找下一个公共元素
            p = p->next;
            q = q->next;
        }
    }

    // 设置链表 C 的末尾标志
    rc->next = NULL;

    // 返回包含公共元素的新链表
    return C;
}

代码逻辑解析¶

1. 初始化阶段¶

创建结果链表：C 是新链表的头节点，不存储数据
设置指针：
p 指向链表 A 的第一个数据节点（A->next）
q 指向链表 B 的第一个数据节点（B->next）
rc 指向结果链表 C 的尾节点，初始时指向头节点

2. 核心算法逻辑¶

利用两个链表都递增有序的特性，采用双指针比较法：

情况1：p->data > q->data
A 的当前元素大于 B 的当前元素
由于 B 是递增的，需要移动 q 指针寻找更大的值
情况2：p->data < q->data
A 的当前元素小于 B 的当前元素
由于 A 是递增的，需要移动 p 指针寻找更大的值
情况3：p->data == q->data
找到公共元素，创建新节点加入结果链表 C
同时移动两个指针继续寻找下一个公共元素

3. 终止条件¶

当其中一个链表遍历完成时，循环结束，因为不会再有新的公共元素。

时间复杂度分析¶

遍历次数：最多遍历 m + n 次（m 是链表 A 的长度，n 是链表 B 的长度）
每次操作：比较和指针移动都是 O(1) 时间
创建节点：最多创建 min(m,n) 个新节点，每次 O(1) 时间

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

空间复杂度分析¶

辅助变量：只使用了常量级别的指针变量 p, q, rc, r，空间复杂度 O(1)
结果链表：虽然创建了新节点存储公共元素，但这是算法要求的输出，不计入空间复杂度分析

因此，空间复杂度为 O(1)（不包括输出链表的空间）。

较难理解部分的说明¶

为什么可以这样比较？¶

关键前提：两个链表都是递增有序的

这使得我们可以使用类似于归并排序中的合并策略：

Text Only

链表 A: 1 -> 3 -> 5 -> 7 -> 9
链表 B: 2 -> 3 -> 6 -> 7 -> 8

比较过程：
1 vs 2: 1 < 2，移动 p 指针
3 vs 2: 3 > 2，移动 q 指针  
3 vs 3: 3 = 3，找到公共元素！创建节点存储 3
5 vs 6: 5 < 6，移动 p 指针
7 vs 6: 7 > 6，移动 q 指针
7 vs 7: 7 = 7，找到公共元素！创建节点存储 7
9 vs 8: 9 > 8，移动 q 指针
q 为 NULL，结束

图解说明¶

Text Only

初始状态:
A: Head -> 1 -> 3 -> 5 -> 7 -> 9 -> NULL
           ↑
           p

B: Head -> 2 -> 3 -> 6 -> 7 -> 8 -> NULL  
           ↑
           q

C: Head -> NULL
           ↑
           rc

过程演示:
步骤1: 1 < 2, 移动 p
步骤2: 3 > 2, 移动 q  
步骤3: 3 = 3, 找到公共元素
       C: Head -> 3 -> NULL
                   ↑
                   rc
步骤4: 5 < 6, 移动 p
步骤5: 7 > 6, 移动 q
步骤6: 7 = 7, 找到公共元素
       C: Head -> 3 -> 7 -> NULL
                       ↑
                       rc

延伸知识点¶

1. 相关算法变体¶

并集操作：

C
// 创建包含两个链表所有元素的有序链表（去重）
LinkList unionList(LinkList A, LinkList B) {
    // 类似逻辑，但遇到相等元素时只添加一次
}

差集操作：

C
// 创建 A-B 的差集
LinkList difference(LinkList A, LinkList B) {
    // 只添加 A 中有但 B 中没有的元素
}

2. 数组版本的实现¶

如果数据存储在数组中：

C
// 数组版本的交集算法
int* arrayIntersection(int A[], int m, int B[], int n, int* resultSize) {
    int* result = (int*)malloc(sizeof(int) * min(m, n));
    int i = 0, j = 0, k = 0;

    while (i < m && j < n) {
        if (A[i] < B[j]) {
            i++;
        } else if (A[i] > B[j]) {
            j++;
        } else {
            result[k++] = A[i];
            i++; j++;
        }
    }

    *resultSize = k;
    return result;
}

3. 处理重复元素的情况¶

如果链表中允许重复元素：

C
// 处理重复元素的交集算法
else { // 相等时
    // 可能需要跳过所有重复元素
    int commonValue = p->data;
    while (p != NULL && p->data == commonValue) p++;
    while (q != NULL && q->data == commonValue) q++;
    // 只添加一次公共值
}

4. 实际应用场景¶

数据库查询：找出两个查询结果的交集
社交网络：找出两个用户共同的好友
文件系统：找出两个目录中的共同文件
推荐系统：基于用户行为的交集分析

这种方法体现了分治思想和有序数据结构的优势，通过利用数据的有序性，避免了暴力比较，实现了高效的交集运算。