当前位置:C++技术网 > 资讯 > 面试题:7 常考考点之单链表一分为二原理剖析

面试题:7 常考考点之单链表一分为二原理剖析

更新时间:2016-05-15 22:47:43浏览次数:1+次

在《数据结构中单链表求集合数组的并集-算上集合数组重合的元素》《数据结构中单链表求集合数组的并集-不算上集合数组重合的元素》《数据结构中单链表求集合数组的交集》等系列描述单链表常见操作的文章中,我们给出了源码。然而并没有解释,在这里,我们就结合本文的中心点"单链表一分为二"来一起描述。

先看看运行结果:

单链表的求并集问题,就是将两个单链表按升序或是降序的顺序排列成一个链表!那么这样的问题的思路是什么样的呢?这个不急,我们先讲讲单链表一分为二的操作原理。在程序员面试金典一书中,有这样的一个问题:
编写代码,以给定值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);
}
你会发现是一样的。没错,其实原理是一样的,我刚开始研究一分为二的时候,就像从求并集开始着手。于是最后查资料结合自己的理解,其实两者的原理是一样的!