参考答案

正确答案：LinkedList Common(LinkedList ABC)∥链表A、链表B和链表c是三个带头结点且结点元素值非递减排列的有序表。本算法使链表A仅留下三个表均包含的结点且结点值不重复释放所有结点{pa=A->next；pb=B->next；pc：C->next；∥pa、pb和pe分别是链表A、B和c的工作指针。pre=A；∥pre是链表A中当前结点的前驱结点的指针while(pa&&pb&&pc)∥当链表A、B和c均不空时查找三链表共同元素{while(pa&&pb)if(pa一>data<pb一>data){U=pa；pa=pa->next；free(U)；}∥结点元素值小时后移指针else if(pa->data>pb->data)pb=pb->next；else if(pa&&pb)∥处理链表A和B元素值相等的结点{while(pc&&pc一>data<pa一>data)pc=pc->next；if(pc){if(pc一>data>pa一>data)∥pc当前结点值与pa当前结点值不等pa后移指针{u=pa；pa=pa->next；free(u)；}else／／pc、pa和pb对应结点元素值相等{if(pre==A){pre->next=pa；pre=pa；pa=pa->next}∥结果表中第一个结点else if(pre->data==pa一>data)／／(处理)重复结点不链人链表A{u=pa；pa=pa->next；free(u)；}else{pre->next=pa；pre=pa；pa=pa->next；}∥将新结点链人链表Apb=pb->next；pc=pc->next；／／链表的工作指针后移}}／／else pc、pa和pb对应结点元素值相等if(pa==null)pre->next=null；／／原链表A已到尾置新链表A表尾else／／处理原链表A未到尾而链表B或链表c到尾的情况{pre->next=null；／／置链表A表尾标记while(pa!=null)／／删除原链表A剩余元素{u=pa；pa=pa一>next；free(u)；}
留下3个链表中的公共数据，首先查找链表A和链表B中公共数据，再去链表c中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O(m+n+p)，在查找每个链表时，指针不能回溯。算法实现时，链表A、链表B和链表C均从头到尾(严格地说链表B、链表C中最多一个到尾)遍历一遍，算法时间复杂度符合O(m+n+p)。算法主要有while(pa&&pb&&pc)。