已知两个链表A和分别表示两个集合,其元素递增排列,请设计算法求出A与B的差集,并存放在A中,同时返回该集合元素的个数.

Question

已知两个链表A和分别表示两个集合,其元素递增排列,请设计算法求出A与B的差集,并存放在A中,
同时返回该集合元素的个数.

Answer 1

int purge_L(LinkList &La,List Lb)
{ //找出有序单链表La和Lb中不同的元素,存放在La中,返回La中元素个数
LNode *pa,*pb,*p,*deb;
int count=0;
p=La;
pa = La->next;
pb = Lb->next;
while ( pa && pb )
{
if ( pa->data < pb->data )
{ // 如果 pa->datadata
p->next = pa; p = pa; pa = pa->next;
}
else if(pa->data== pb->data)
{
p->next=pa->next;
free(pa);
pa=p->next;
deb=pb;
pb=pb->next;
free(deb);
}
else{
p->next = pb; p = pb; pb = pb->next;
}
count++;
}
// 插入剩余段
if(pa)
{
p->next = pa ;
while(pa)
{
count++;
pa=pa->next;
}
}else{
p->next = pb ;
while(pb)
{
count++;
pb=pb->next;
}
}
free (Lb); // 释放 Lb 的头结点
return count;
} // purge_L