先看看运行结果:
单链表的求并集问题,就是将两个单链表按升序或是降序的顺序排列成一个链表!那么这样的问题的思路是什么样的呢?这个不急,我们先讲讲单链表一分为二的操作原理。在程序员面试金典一书中,有这样的一个问题:
编写代码,以给定值x为基准将单链表分隔成两部分,所有小于x的结点排在大于或等于x的结点的前面。
这个面试题,其实就是让你将链表一分为二。刚刚看的时候,我还不是很理解,然后上网搜,看看能不能得到启发。结果,大多数都是直接把书上那段代码给拷过来,重点不在这里,重点是,树上那段代码是java的,然后只有一个人写的是C++的代码,关键是那个人也是直接照抄过来的!!!对比书上的代码,没有变动......我当时脑子里有无数头草泥马飞过......
后来就只能靠自己了。然后,我就想起来了,既然这里是求一分为二,我之前写过合二为一的代码啊!然后,我就从之前的那个求并集的代码入手分析。结果分析出了和书上不一样的代码,后来决定相信自己,按照自己的思路写代码,不看书上的那个我看不懂的java代码......
可是又遇到一个问题。既然是一分为二,那么最少应该有两个单链表,后来,我一想,还是分开点,这样更清晰!就建立了三个单链表。其中一个单链表存入数据,另外两个分别存入小于x的单链表A与大于等于x的单链表B。那么问题来了,另外两个单链表A,B,我该如何初始化?又来一想,原来是自己习惯性了没有依靠之前写过的初始化链表的函数,没有调用这个函数。所以,就被坑了!在这里,给大家提个醒!好了下面给出代码:
void pri(LinkList H)
{
LinkList p;
p=H->next;
while(p)
{
cout<<p->data<<" ";
p=p->next;
}
}
void fengecaozuo(LinkList H,LinkList A,LinkList B,int x)
{
LinkList pa,pb,pc;
pc=H->next;
pa=A;
pb=B;
while(pc)
{
if(pc->data<x)
{
pa->next=pc;
pa=pc;//注释掉这行,运行下面那行也行!!!
//pa=pa->next;
pc=pc->next;
}
else
{
pb->next=pc;
pb=pc;//注释掉这行,运行下面那行也行!!!
//pb=pb->next;
pc=pc->next;
}
}
pa->next=NULL;
pb->next=NULL;
cout<<"A链表:"<<endl;
pri(A);
cout<<"B链表:"<<endl;
pri(B);
return ;
}
对于A,B两个单链表,我并没有调用初始化函数,而是直接在main函数中:LinkList A,B;
A=(LinkList)malloc(sizeof(LinkList));
B=(LinkList)malloc(sizeof(LinkList));
就是直接给A,B分配空间。当满足操作的时候,我就给两个链表的对象赋值。从头结点下的第一个结点开始,我们将pc所对应的结点赋值给他们,自然,你就需要递增pc结点。与此同时,递增的还有pa,pb结点,否则的话,我们怎么给整个A,B链表赋值!注意看上面的程序的注释。那么我们看看单链表求并集的程序代码:
void MergeList(LinkList A, LinkList B, LinkList *C)
{
ListNode *pa, *pb, *pc;
pa=A->next;
pb=B->next;
*C=A;
(*C)->next=NULL;
pc=*C;
while(pa&& pb)
{
if(pa->data <= pb->data)
{
pc->next=pa;
pc=pa;
pa=pa->next;
}
else
{
pc->next=pb;
pc=pb;
pb=pb->next;
}
}
pc->next=pa ? pa: pb;
free(B);
}
你会发现是一样的。没错,其实原理是一样的,我刚开始研究一分为二的时候,就像从求并集开始着手。于是最后查资料结合自己的理解,其实两者的原理是一样的!