设计一个函数
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中移除