网红营销优势_企业年报查询官网入口_淘宝指数入口_新闻最新消息

三个带头结点的单链表，元素均递增有序（假设每个单链表不存在数据值相同的结，但三个表中成长数据相同的结点）。设计一个算法，使第一个链表中仅留下三个表中均包含的结点，且没有数据值相同的结点，并释放LA中其他结点。要求时间复杂度为O(m+n+p)，m,n和p分别为三个表的长度。

思想：先以单链表LA 的头节点作为一个空表，r指向这个链表的尾结点，遍历LA中的数据结点，判断他是否在LB和LC中，若同时在，则表示是公共结点，连接到r后，否则删除。

代码：

void ComNode(LinkNode &LA，LinkNode LB,LinkNode LC){LinkNode *pa=LA->next,*pb=LB->next,pc=LC->next,*r,*q;LA->next=NULL;//此时LA作为新建链表的头结点 r=LA;//指向 新建链表的尾结点 while(pa!=NULL){//与B表进行比较 while(pb!=NULL&&pa->data>pb->data){pb=pb->next;}//与A表进行比较 while(pc!=NULL&&pa->data>pc->data){pc=pc->next;}//找到公共结点，进行插入 if(pb!=NULL&&pc!=NULL&&pa->data=pb->data&&pa->data==pc->data){r->next=pa;r=pa;pa=pa->next;}else{//不是公共结点进行删除 q=pa;pa=pa->next;free(q)}}r->next=NULL;//尾结点置空 
} 

时间复杂度O（m+n+p），空间复杂度O（1）