已知两个链表A和B分别表示两个集合,其元素递增排列。编制函数,求A与B 的交集,并存放于A链表中。
算法思想:用归并的思想,设置两个工作指针pa和pb,对两个链表进行归并扫描,只有同时出现在两集合中的元素才链接到结果表中且仅保留一个,其他的结点全部释放。当一个链表遍历完毕后,释放另一个表中剩下的全部结点。
LinkList Union(LinkList &la,LinkList &lb) {
pa=la->next; //设工作指针分别为pa和pb
pb=lb->next;
pc=la; //结果表中当前合并结点的前驱指针
while(pa&&pb){
if(pa->data==pb->data) { //交集并入结果表中
pc->next=pa; //A中结点链接到结果表
pc=pa;
pa=pa->next;
u=pb; //B中结点释放
pb=pb->next;
free(u);
}
else if (pa->data<pb->data) { //若A中当前结点值小于B中当前结点值
u=pa;
pa=pa->next; //后移指针
free(u) ; //释放A中当前结点
}else{ //若B中当前结点值小于A中当前结点值
u=pb;
pb=pb->next; //后移指针
free (u) ; //释放B中当前结点
}
} //while 结束
while(pa){ //B已遍历完,A未完
u=pa;
pa=pa->next;
free (u) ; //释放A中剩余结点
}
while(pb){ //A已遍历完,B未完
u=pb;
pb=pb->next;
free(u) ; //释放B中剩余结点
}
pc->next=NULL; //置结果链表尾指针为NULL
free (lb) ; //释放B表的头结点
return la;
}
链表归并类型的题在各学校历年真题中出现的频率很高,故应扎实掌握此类问题的思想。该算法的时间复杂度为O(len1+len2),空间复杂度为O(1)。