设计一个函数 其功能是求Lb和La的交集,且将交集的结果置于La中,其中La和Lb的元素均为非递减有序排列,求交集后的La的元素也为非递减有序排列。

设计一个函数
void Intersection (List La, List Lb)
其功能是求Lb和La的交集,且将交集的结果置于La中,其中La和Lb的元素均为非递减有序排列,求交集后的La的元素也为非递减有序排列。La和Lb是带头结点的单向链表。

struct Node
{
    int value;
    struct Node *next;
};

typedef struct Node List;

void intersection(List La, List Lb)
{
    struct Node *prev = &La;
    struct Node *p = La.next;
    struct Node *q = Lb.next;
    while (p)
    {
        while (q && p->value < q->value)
            q = q->next;
        if (q && p->value == q->value)
        {
            prev = p;
            p = p->next;
        }
        else
        {
            prev->next = p->next;
            free(p);
            p = prev->next;
        }
    }
}

把 La 中的每个元素和 Lb 中的元素进行比较,不用轮询完,遇到大于等于自己的Lb元素就可以停止,记录下Lb中的这个索引,下一个La元素直接从这个位置开始查找,找到相同的保留,否则从La中移除