今天去網上看了一下09年的考研試題，看見該題目(圖片)：
先來定義結點（為了簡便，省略set/get)：
public class Node
{
public int data;
public Node link;
}
我能想到的兩種解法，一個基于遞歸：
遞歸版的思路就是，基于當前結點，如果后一個是倒數第K-1,那么當前結點是所求，若不然，返回當前是倒數第幾個。
public int printRKWithRecur(Node head,int k)
{
if(k==0||head==null||head.link==null)return 0;
if(_recurFind(head.link,k)>=k)return 1;
return 0;
}
private final int _recurFind(Node node, int k) {
if(node.link==null)
{
return 1;
}
int sRet=_recurFind(node.link,k);
if(sRet==k-1)
{
System.out.println("Got:"+node.data);
return k;
}
return sRet+1;
}
對每個結點，該算法都只訪問一次，因此復雜度O(N).
第二解法，相對遞歸來說，這種方法可以算是消除遞歸版，而且從某種意義上來說比遞歸更高效，跟省空間，遞歸版實際上是把回溯的數據存在棧上，而版方法是自己存儲，且利用數組實現一個循環隊列，只存儲K個元素。
public static class CycleIntQueue
{
int[] datas;
int top=0;
int num=0;
public CycleIntQueue(int n)
{
datas=new int[n];
}
public void push(int i)
{
datas[(top++)%datas.length]=i;
num++;
}
public int numPushed()
{
return num;
}
public int getButtom()
{
return datas[top%datas.length];
}
}
public int printRKWithCycleQueue(Node head,int k)
{
if(k==0||head==null)return 0;
CycleIntQueue queue=new CycleIntQueue(k);
Node cur=head.link;
while(cur!=null)
{
queue.push(cur.data);
cur=cur.link;
}
if(queue.numPushed()<k)return 0;
System.out.println("Got:"+queue.getButtom());
return 1;
}
本算法，都每個結點也只放一次，另外進行一次入隊操作，該操作復雜度O(1),從而，整個算法復雜度仍是O(N).