今天去网上看了一下09年的考研试题,看见该题目(图片):
先来定义结点(为了简便,省略set/get):
publicclassNode
{
publicintdata;
publicNodelink;
}
我能想到的两种解法,一个基于递归:
递归版的思路就是,基于当前结点,如果后一个是倒数第K-1,那么当前结点是所求,若不然,返回当前是倒数第几个。
publicintprintRKWithRecur(Nodehead,intk)
{
if(k==0||head==null||head.link==null)return0;
if(_recurFind(head.link,k)>=k)return1;
return0;
}
privatefinalint_recurFind(Nodenode,intk){
if(node.link==null)
{
return1;
}
intsRet=_recurFind(node.link,k);
if(sRet==k-1)
{
System.out.println(“Got:”+node.data);
returnk;
}
returnsRet+1;
}
对每个结点,该算法都只访问一次,因此复杂度O(N)。
第二解法,相对递归来说,这种方法可以算是消除递归版,而且从某种意义上来说比递归更高效,跟省空间,递归版实际上是把回溯的数据存在栈上,而版方法是自己存储,且利用数组实现一个循环队列,只存储K个元素。
publicstaticclassCycleIntQueue
{
intdatas;
inttop=0;
intnum=0;
publicCycleIntQueue(intn)
{
datas=newint[n];
}
publicvoidpush(inti)
{
datas[(top++)%datas.length]=i;
num++;
}
publicintnumPushed()
{
returnnum;
}
publicintgetButtom()
{
returndatas[top%datas.length];
}
}
publicintprintRKWithCycleQueue(Nodehead,intk)
{
if(k==0||head==null)return0;
CycleIntQueuequeue=newCycleIntQueue(k);
Nodecur=head.link;
while(cur!=null)
{
queue.push(cur.data);
cur=cur.link;
}
if(queue.numPushed()<k)return0;
System.out.println(“Got:”+queue.getButtom());
return1;
}
本算法,都每个结点也只放一次,另外进行一次入队操作,该操作复杂度O(1),从而,整个算法复杂度仍是O(N).
一起交流学习请访问:Tore_m_1206686_21115_1_1.html”>http://www.shangxueba.com/sTore_m_1206686_21115_1_1.html
未经一番寒彻骨,焉得梅花扑鼻香