虽然研究生已毕业,但看到有一些难度的研究生考试题还是忍不住要做做,本文给出了09年研究生入学考试的一道数据结构题的Java实现。该题的描述如下图所示。
该题的两种实现一位朋友已经完成了,详见
递归和非递归实现 。在本文将给出另外一种算法,该算法的空间复杂度为O(1),时间复杂度为O(n)。这在空间复杂度和时间复杂度上应该是比较优化了。
本算法的基本思想如下:
既然是查找倒数第K个结点(注意,不是正数,否则就没什么可讨论的了),而且链表是单向的,还不能改变表结构,这就意味着只能从前往后扫描结点。我们首先要知道这个链表有多少个结点(如果总结点数都不知道,何谈倒数?),这个非常简单,只要从头扫描一下链表,再计一下数即可。
在同一时间从事多项工作会大大提升效率,当然,扫描链表也不例外,在扫描链表的同时,还需要做一些其他的工作。既然只能从前向后扫描链表,而且要求倒数第K个结点,那就让我们把这个链表按长度为K分成若干块,而最后扫描的结果要么结点数是K的整数倍(模为0),要么余数(模)不为0(多出几个结点,多出的结点数小于K)。
先看看第二种情况。
假设有12个结点的链表,每一个结点的值从前往后分别是1至12,如下所示:
1 2 3 4 5 6 7 8 9 10 11 12
假设我们要求倒数第5个结点,我们直接就可以看出结果是8。那么用程序如何处理呢?
先按长度为5将上面的结点分成三个区域,如下:
1 2 3 4 5 6 7 8 9 10 11 12
注意,不是物理分,而是使用变量来保存区域的边界(也就是区域最后一个结点的对象)。
从上面的分隔可以看出,最后剩下两个结点,既然是求倒数第5个,而最后剩下了两个,那么还缺5-2=3个,因此,只需要从倒数第二个块(6 78 910)略过前两个,第三个结点(8)就是我们要求的结果,而5就是题中的k,2就是结点数与k的模,因此,可以推出一个公式,倒数第k个结点就是按长度为k按分成的若干块中的第二块的第(结点数 % k+ 1)个结点。
下面来看看(结点数 % k)为0的情况。假设上面的例子中的k为4,正确的输出结果应为9,分块如下:
1 2 3 4 5 6 7 8 9 10 11 12
从上面的三个块可以看出,结果正好是最后一个块的第一个结点,这时mod为0(mod=结点数 % k),因此,在这种情况也可以使用上面的公式,只是变成了最后一个块。
根据上面的基本思想可以设两个指针,p1和p2,其中p1最终指向倒数第2个完整块,p2最终指向倒数第1个完整块,对于第一种情况,p1指向5,p2指向10,这时可以使p1向后移动(k -mod)个结点即可(从5移动3个正好是8)。而对于第二种情况,p1指向8,p2指向12,而mod=0,这时的结果仍然是mod+1,也就是p1向后移动1个结点就是所求的结果。为了满足(k=结点数)的情况,需要将p1的初始值设为头结点,这样如果(k=结点数),就直接从头结点向后移动一个结点就是最后的结果,如上面的例子求倒数第12个结点,也就是求正数第1个结点。
下面是这个算法的具体实现(包括核心算法、生成链表及调用核心算法的代码):
publicclassTest
{
staticclassNode
{
publicintdata;
publicNodenextNode;
}
//////////////////////////////////////////
//核心算法
privatestaticintfindNode(NodeheadNode,intk)
{
Nodep=headNode,p1=headNode,p2=null;
intcount=0;//表示结点数
while(p.nextNode!=null)
{
p=p.nextNode;
count++;
//遇到k的整数位个结点,进行分块
if(count%k==0)
{
if(p2!=null)
p1=p2;
p2=p;
}
}
//k超过链表结点数,未找到,返回0
// 此处也可以用k > count来判断
if(p2==null)
{
return0;
}
else
{
intmod=count%k;
intoffset=mod+1;//任何情况下,最终结果都是p1指向的结点向后移动(mod+1)个结点
for(inti=0;i<offset;i++)
p1=p1.nextNode;
System.out.println(p1.data);
return1;
}
}
////////////////////////////////////////
publicstaticvoidmain(String[]args)throwsException
{
//产生一个包含1个头结点和120个结点的链表
NodeheadNode=newNode();
Nodep=headNode;
for(inti=0;i<120;i++)
{
p.nextNode=newNode();
p.nextNode.data=i+1;
p=p.nextNode;
}
p.nextNode=null;
//开始查找倒数第k个结点,如果找到,返回1,并输出结点的data值
System.out.println(findNode(headNode,12));
}
}
上面程序的输出结果如下:
109
1
读者也可以使用其他的测试用例来测试上面的程序。
本算法从空间复杂度O(1)和时间复杂度O(n)的综合指标基本上算是比较优化了,如果哪位读者还有更简单和快速的算法,请跟贴!!
分享到:
相关推荐
《算法与数据结构考研试题精析》收集了自1992年以来国内60余所重点高校和科学院、所300多套硕士研究生入学“算法与数据结构”考试试卷的1600多道试题,并给出了参考答案和分析。《算法与数据结构考研试题精析》可以...
算法与数据结构历年考研试题分析与答案解析。主要就是拿来练练手
考研数据结构1800试题详解 考研 数据结构 1800试题 详解
其实1800题是2001年推出来的,当时编者把电子版免费分享给大家,却很少有人知道它也有纸质版本就是《算法与数据结构考研试题精析》。第二版是2007年最新出版的,对里面的题目进行了大量的更新,去掉了一些比较过时和...
算法与数据结构考研试题精析【第3版】【书签完整】.zip
数据结构1800题 数据结构1800题
北京师范大学08年考研程序设计与数据结构试题
2016-2018南昌大学考研数据结构试题和答案,2016-2018南昌大学考研数据结构试题和答案,2016-2018南昌大学考研数据结构试题和答案
数据结构\数据结构考研试题精选及答案数据结构\数据结构考研试题精选及答案数据结构\数据结构考研试题精选及答案
历年数据结构考研题及答案,分章节管理第一章、绪论 试题 参考答案 第二章、线性表 试题 参考答案 第三 章、栈和队列 试题 参考答案 第四章、串 试题 参考答案 第五章、数组和广义表 试题 参考答案 第六章、...
全国所有高校数据结构考研试题,1800道题,从90年代开始!
算法与数据结构考研试题精析(第二版) 传说中的1800题第二版
北交计算机考研数据结构试题,有三份,分别是01、05、07
数据结构考研试题,内含1800道数据库考研试题及答案详解,拿下这1800道题,考研数据结构不再是问题
算法与数据结构考研试题精析第二版.rar算法与数据结构考研试题精析第二版.rar