AC210-找出两个递增有序单链表的公共元素，存放到A链表中

代码实现

// 函数 common：找出两个递增有序单链表的公共元素，存放到A链表中
// 利用A链表的原有节点空间，实现交集操作
void common(LinkList A, LinkList B) {
    LinkList p = A, q = B->next; // p指向A链表的头节点，q指向B链表的第一个数据节点

    // 当A链表还有数据节点且B链表还未遍历完时继续循环
    while (p->next != NULL && q != NULL) {
        // 如果A链表当前节点的值大于B链表当前节点的值
        if (p->next->data > q->data) {
            q = q->next; // B链表指针向后移动，寻找更大的值
        }
        // 如果A链表当前节点的值小于B链表当前节点的值
        else if (p->next->data < q->data) {
            LinkList r = p->next;     // r指向要删除的A链表节点
            p->next = r->next;        // 从A链表中删除该节点
            free(r);                  // 释放该节点的内存
            // 注意：此时p指针不移动，因为还要检查新连接的节点
        }
        // 如果A链表当前节点的值等于B链表当前节点的值（找到公共元素）
        else {
            p = p->next; // 保留该节点，p指针向后移动
            q = q->next; // B链表指针也向后移动
        }
    }

    // 如果A链表还有剩余节点，将它们全部删除
    // 因为这些节点在B链表中找不到对应的公共元素
    if (p->next != NULL) {
        LinkList current = p->next; // current指向第一个要删除的节点
        p->next = NULL;             // 将A链表截断

        // 释放剩余所有节点的内存
        while (current != NULL) {
            LinkList temp = current;
            current = current->next;
            free(temp);
        }
    }
}

---

代码逻辑解析

1. 初始化指针：
2. p 指向链表A的头节点，用于遍历和修改链表A

3. q 指向链表B的第一个数据节点（跳过头节点）

4. 三情况比较：

5. A > B：A链表当前节点值较大，B链表指针后移，寻找更大的值
6. A < B：B链表当前节点值较大，删除A链表当前节点

7. A = B：找到公共元素，两个指针都后移

8. 删除策略：

9. 通过修改指针连接关系删除不需要的节点

10. 立即释放被删除节点的内存，避免内存泄漏

11. 清理剩余节点：

12. 循环结束后，如果A链表还有剩余节点，说明这些节点不是公共元素
13. 将这些节点全部删除并释放内存

---

时间复杂度分析

• 循环次数：
• 每次循环至少会移动一个指针（p或q）
• 最多执行 m + n 次循环（m是A链表长度，n是B链表长度）
• 每次操作都是常数时间

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

---

空间复杂度分析

• 额外空间使用：
• 只使用了常量级别的指针变量（p, q, r, current, temp）
• 没有使用与输入规模相关的额外空间
• 通过重用A链表的原有节点空间实现交集操作

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

---

较难理解部分的说明

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

else if (p->next->data < q->data) {
    LinkList r = p->next;     // 要删除的节点
    p->next = r->next;        // 绕过被删除节点
    free(r);                  // 释放内存
    // p指针不移动！
}

这是因为删除节点后，p->next 指向了新的节点，需要继续检查这个新节点是否满足条件。

图解说明

假设：

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

执行过程：

初始状态:
p -> A, q -> 2

步骤1: A[1] < B[2] 
删除A的节点1，p仍指向A
链表A: A -> 3 -> 5 -> 7 -> 9 -> NULL

步骤2: A[3] > B[2]
q后移，q -> 3

步骤3: A[3] = B[3]
找到公共元素3，p和q都后移
链表A: A -> 3 -> 5 -> 7 -> 9 -> NULL

步骤4: A[5] > B[3]  
q后移，q -> 5

步骤5: A[5] = B[5]
找到公共元素5，p和q都后移
链表A: A -> 3 -> 5 -> 7 -> 9 -> NULL

步骤6: A[7] > B[5]
q后移，q -> 6

步骤7: A[7] > B[6] 
q后移，q -> NULL

循环结束，删除A链表剩余节点7和9
最终结果: A -> 3 -> 5 -> NULL

---

延伸知识点

1. 链表交集的其他实现方法

方法一：使用辅助空间

void commonWithHash(LinkList A, LinkList B) {
    // 使用哈希表记录B链表的所有元素
    // 遍历A链表，保留存在于哈希表中的节点
    // 时间复杂度O(m+n)，空间复杂度O(n)
}

方法二：创建新链表

LinkList createNewCommonList(LinkList A, LinkList B) {
    // 创建全新的链表存储公共元素
    // 不修改原链表结构
    // 时间复杂度O(m+n)，空间复杂度O(k)，k为公共元素个数
}

2. 相关链表操作问题

并集操作：

// 找出两个有序链表的所有元素（去重）
void unionList(LinkList A, LinkList B) {
    // 保留所有元素，相同元素只保留一份
}

差集操作：

// 找出在A中但不在B中的元素
void differenceList(LinkList A, LinkList B) {
    // 类似于当前算法，但删除策略相反
}

3. 边界条件处理

需要考虑的特殊情况： - 空链表：A或B为空时的处理 - 完全无交集：一个链表的所有元素都小于另一个链表的最小元素 - 完全包含：一个链表完全包含另一个链表 - 重复元素：如果允许重复元素的存在

4. 实际应用场景

• 数据库操作：两个有序数据表的交集查询
• 集合运算：数学集合的交集操作
• 数据同步：找出两个数据源的共同数据
• 版本控制：找出两个版本中的共同修改

这种方法充分利用了链表的有序性和指针操作的灵活性，通过巧妙的指针移动策略实现了高效的交集运算，是链表操作中的经典算法。