09考研数据结构试题解法大比拼

今天去网上看了一下09年的考研试题，看见该题目(图片)：
我的解法：
先定义结点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;
}第二解法，相对递归来说，这种方法可以算是消除递归版，而且从某种意义上来说比递归更高效，跟省空间，递归版实际上是把回溯的数据存在栈上，而版方法是自己存储，且利用数组实现一个循环队列，只存储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;
}