两个递增链表的交集

已知两个链表A和B分别表示两个集合.其元素递增排列. 设计一个算法,用于求出A与B的交集,并存储在A链表中;

示例:

输入：2->4->6->8,  4->6->8->10
输出：4->6->8

解题思路：

1. 只有同时出现在两集合中的元素才出现在结果表中，合并后的新表使用头指针Lc指向。pa和pb分别是链表La和Lb的工作指针,初始化为相应链表的第一个结点;
2. 遍历，判断节点元素是否相等
   -- 相等，取A表中元素，删除B表中元素
   -- 不相等，删除最小的元素
3. 当链表有一个先到表尾，依次删除另一个非空表中的所有元素；
4. 释放链表B;

复杂度分析：

• 时间复杂度O(n)
• 空间复杂度 O(1)

代码：

typedef struct Node{
    int data;
    struct Node *next;
} Node;
typedef struct Node * LinkList;

void Intersection(LinkList *La, LinkList *Lb, LinkList *Lc) {
    LinkList pa, pb, pc, temp;
    pa = (*La)->next;
    pb = (*Lb)->next;
    *Lc = pc = *La;
    while (pa && pb) {
        if (pa->data < pb->data) {
            temp = pa->next;
            free(pa);
            pa = temp;
        } else if (pa->data > pb->data) {
            temp = pb->next;
            free(pb);
            pb = temp;
        } else {
            pc->next = pa;
            pc = pa;
            pa = pa->next;

            temp = pb;
            pb = pb->next;
            free(temp);
        }
    }
    
    LinkList pd = pa ? pa: pb;
    while (pd) {
        temp = pd;
        pd = pd->next;
        free(temp);
    }
    
    pc->next = NULL;
    free(*Lb);
}