本文给出了09年研究生入学考试的一道数据结构题的Java实现。该题的描述如下图所示。

先来定义结点（为了简便，省略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;
    }
    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).

在本文提出利用分块思想解决问题，该算法的空间复杂度为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 7 8 9 10）略过前两个，第三个结点（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个结点。
下面是这个算法的具体实现（包括核心算法、生成链表及调用核心算法的代码）：

     public class Test
    {
    static class Node
    {
        public int data;
        public Node nextNode;
    }
    //  核心算法
    private static int findNode(Node headNode, int k)
    {
        Node p = headNode, p1 = headNode, p2 = null; 
        int count = 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) 
        {
            return 0;
        }
        else
        {
            int mod = count % k;
            int offset = mod + 1;  // 任何情况下，最终结果都是p1指向的结点向后移动(mod + 1)个结点
            for (int i = 0; i < offset; i++)
                p1 = p1.nextNode;
            System.out.println(p1.data);
            return 1;
        }
    }
    public static void main(String[] args) throws Exception
    {
        //产生一个包含1个头结点和120个结点的链表
        Node headNode = new Node();
        Node p = headNode;
        for (int i = 0; i < 120; i++)
        {
            p.nextNode = new Node();
            p.nextNode.data = i + 1;
            p = p.nextNode;
        }
        p.nextNode = null;
        //  开始查找倒数第k个结点，如果找到，返回1，并输出结点的data值
        System.out.println(findNode(headNode, 12));
    }
}

上面程序的输出结果如下：
109
1
读者也可以使用其他的测试用例来测试上面的程序。

注：来自 “ ITPUB博客 ” ，
链接：http://blog.itpub.net/12921506/viewspace-541475/