1.设A和B是两个单链表(带头节点),其中元素递增有序。设计一个算法从A和B的公共元素产生C,不破坏AB节点
思路:
1.A,B表左端对齐
1.1左端元素相等,申请一个节点尾插到新表,A,B都往后一位
1.2左端元素不相等,使更小的元素所处链表后移动一位
1.3重复前两步直到一表为空
A,B带头节点
ListNode*jiao(ListNode*A,ListNode*B)
{
ListNode*subA=A->next;
ListNode*subB=B->next;
ListNode*C=new ListNode(-1);
C->next=NULL;
ListNode*tailC=C; //C的尾指针
while(subA&&subB)
{
if(subA->val==subB->val)
{
ListNode*nod=new ListNode(subA->val);
tailC->next=nod;
tailC=tailC->next;
subA=subA->next;
subB=subB->next;
}
else if(subA->val<subB->val)
{
subA=subA->next;
}
else
{
subB=subB->next;
}
}
tailC->next=NULL;
return C;
}
2.设A和B是两个单链表(带头节点),其中元素递增有序。设计一个算法从A和B的公共元素存于A中
思路:
采用归并的思想,设置两个工作指针pa,pb,对两个链表归并扫描,只有同时出现在两个集合中
的元素才链接到结果表中且只保存一个,其他节点全部释放,当一个链表遍历完毕后,释放
另一个表中所有元素
A,B带头节点
ListNode* Union(ListNode* &la,ListNode* &lb)
{
ListNode*pa=la->next;
ListNode*pb=lb->next;
ListNode*pc=la; //la的尾指针
ListNode*u;
while(pa&&pb)
{
if(pa->val==pb->val)
{
pc->next=pa;
pc=pc->next;
pa=pa->next;
u=pb;
pb=pb->next;
delete(u);
}
else if(pa->val<pb->val)
{
u=pa;
pa=pa->next;
delete(u);
}
else
{
u=pb;
pb=pb->next;
delete(u);
}
}
while(pa)
{
u=pa;
pa=pa->next;
delete(pa);
}
while(pb)
{
u=pb;
pb=pb->next;
delete(pb);
}
pc->next=NULL;
delete(lb);
return la;
}
3.查询A-B的差集.存入A中
代码
ListNode*diff(ListNode*A,ListNode*B)
{
ListNode*pc=A; //A的尾指针
ListNode*pa=A->next;
ListNode*pb=B->next;
while(pa&&pb)
{
if(pa->val==pb->val)
{
pa=pa->next;
pb=pb->next;
}
else if(pa->val>pb->val)
{
pb=pb->next;
}
else
{
pc->next=pa;
pc=pc->next;
pa=pa->next;
}
}
pc->next=NULL;
if(pa)
{
pc->next=pa;
}
return A;
}
4.A与B的并集返回A(AB都带头节点)
代码
ListNode*bin(ListNode*A,ListNode*B)
{
ListNode*pa=A->next;
ListNode*pb=B->next;
ListNode*pc=A; //A的尾巴指针
while(pa&&pb)
{
if(pa->val<pb->val)
{
pc->next=pa;
pc=pc->next;
pa=pa->next;
}
else if(pa->val>pb->val)
{
pc->next=pb;
pc=pc->next;
pb=pb->next;
}
else
{
pc->next=pa;
pc=pc->next;
pa=pa->next;
pb=pb->next;
}
}
pc->next=NULL;
if(pa)
{
pc->next=pa;
}
if(pb)
{
pc->next=pb;
}
return A;
}
1.求A,B交集(A,B都无序)
代码
//A,B带头结点,结果最后保留在A
ListNode*bin(ListNode* &A,ListNode*B)
{
ListNode*la=A; //A的工作指针
ListNode*lb; //B的工作指针
ListNode*p; //用于删除A中不是交集中的点
while(la->next) //依次判断A中的元素是否在B中出现过
{
int t=1;
//每次从B的头指针开始判断
lb=B->next;
while(lb)
{
//如果都出现,结束循环,保留A中这个点
if(la->next->val==lb->val)
{
t=0;
break;
}
lb=lb->next;
}
//如果未出现,则删除A中这个点
if(t==1)
{
p=la->next;
la->next=p->next;
delete(p);
}
//如果都出现,结束循环,保留A中这个点,A的工作指针往后移东即可
else
{
la=la->next;
}
}
return A;
}
2.求差
代码
//与求交集相反的处理
ListNode*diff(ListNode*A,ListNode*B)
{
ListNode*pa=A;
ListNode*pb;
ListNode*q;
while(pa->next)
{
pb=B->next;
int t=1;
while(pb)
{
if(pa->next->val==pb->val)
{
t=0;
break;
}
pb=pb->next;
}
if(t==1)
{
pa=pa->next;
}
else
{
q=pa->next;
pa->next=q->next;
delete(q);
}
}
return A;
}
3.求并
代码
//求并集(双重循环,将A中有的在B中删除,然后连接A,B)
ListNode*Union(ListNode*A,ListNode*B)
{
ListNode*pa=A;
ListNode*pb;
while(pa->next) // 遍历链表La 始终使用指针的下一个数据
{
pb=B;
while(pb->next)
{
if(pa->next->val==pb->next->val)
{
pb->next=pb->next->next; // 对集合B中的元素进行修改
}
else
{
pb=pb->next;
}
}
pa=pa->next;
}
pa->next=B->next; // 将集合A与集合B连接
return A;
}