今天去網(wǎng)上看了一下09年的Java考研試題，看見該題目（圖片）：

先來定義結(jié)點(diǎn)（為了簡便，省略set/get）：

public class Node  
{  
 public int data;  
 public Node link;  
}  

對于這個Java考研試題，我能想到的兩種解法，一個基于遞歸：

遞歸版的思路就是，基于當(dāng)前結(jié)點(diǎn)，如果后一個是倒數(shù)第K-1，那么當(dāng)前結(jié)點(diǎn)是所求，若不然，返回當(dāng)前是倒數(shù)第幾個。

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;  
    } 

對每個結(jié)點(diǎn)，該算法都只訪問一次，因此復(fù)雜度O（N）。

第二解法，相對遞歸來說，這種方法可以算是消除遞歸版，而且從某種意義上來說比遞歸更高效，跟省空間，遞歸版實(shí)際上是把回溯的數(shù)據(jù)存在棧上，而版方法是自己存儲，且利用數(shù)組實(shí)現(xiàn)一個循環(huán)隊(duì)列，只存儲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()return 0;  
          
        System.out.println("Got:"+queue.getButtom());  
        return 1;  
    } 

本算法，都每個結(jié)點(diǎn)也只放一次，另外進(jìn)行一次入隊(duì)操作，該操作復(fù)雜度O(1),從而，整個算法復(fù)雜度仍是O(N).

對于此Java考研試題還有另外一種算法，該算法的空間復(fù)雜度為O（1），時間復(fù)雜度為O（n）。這在空間復(fù)雜度和時間復(fù)雜度上應(yīng)該是比較優(yōu)化了。

本算法的基本思想如下：既然是查找倒數(shù)第K個結(jié)點(diǎn)（注意，不是正數(shù)，否則就沒什么可討論的了），而且鏈表是單向的，還不能改變表結(jié)構(gòu)，這就意味著只能從前往后掃描結(jié)點(diǎn)。我們首先要知道這個鏈表有多少個結(jié)點(diǎn)（如果總結(jié)點(diǎn)數(shù)都不知道，何談倒數(shù)？），這個非常簡單，只要從頭掃描一下鏈表，再計(jì)一下數(shù)即可。

在同一時間從事多項(xiàng)工作會大大提升效率，當(dāng)然，掃描鏈表也不例外，在掃描鏈表的同時，還需要做一些其他的工作。既然只能從前向后掃描鏈表，而且要求倒數(shù)第K個結(jié)點(diǎn)，那就讓我們把這個鏈表按長度為K分成若干塊，而最后掃描的結(jié)果要么結(jié)點(diǎn)數(shù)是K的整數(shù)倍（模為0），要么余數(shù)（模）不為0（多出幾個結(jié)點(diǎn)，多出的結(jié)點(diǎn)數(shù)小于K）。

先看看第二種情況。

假設(shè)有12個結(jié)點(diǎn)的鏈表，每一個結(jié)點(diǎn)的值從前往后分別是1至12，如下所示：

1  2  3  4  5  6  7  8  9  10  11 12

假設(shè)我們要求倒數(shù)第5個結(jié)點(diǎn)，我們直接就可以看出結(jié)果是8.那么用程序如何處理呢？

先按長度為5將上面的結(jié)點(diǎn)分成三個區(qū)域，如下：

1 2 3 4 5   6 7 8 9 10   11 12

注意，不是物理分，而是使用變量來保存區(qū)域的邊界（也就是區(qū)域最后一個結(jié)點(diǎn)的對象）。

從上面的分隔可以看出，最后剩下兩個結(jié)點(diǎn)，既然是求倒數(shù)第5個，而最后剩下了兩個，那么還缺5-2=3個，因此，只需要從倒數(shù)第二個塊（6 7 8 9 10）略過前兩個，第三個結(jié)點(diǎn)（8）就是我們要求的結(jié)果，而5就是題中的k，2就是結(jié)點(diǎn)數(shù)與k的模，因此，可以推出一個公式，倒數(shù)第k個結(jié)點(diǎn)就是按長度為k按分成的若干塊中的第二塊的第（結(jié)點(diǎn)數(shù) % k+ 1）個結(jié)點(diǎn)。

下面來看看（結(jié)點(diǎn)數(shù) % k）為0的情況。假設(shè)上面的例子中的k為4，正確的輸出結(jié)果應(yīng)為9，分塊如下：

1 2 3 4  5 6 7 8  9 10 11 12

從上面的三個塊可以看出，結(jié)果正好是最后一個塊的第一個結(jié)點(diǎn)，這時mod為0（mod=結(jié)點(diǎn)數(shù) % k），因此，在這種情況也可以使用上面的公式，只是變成了最后一個塊。

根據(jù)上面的基本思想可以設(shè)兩個指針，p1和p2，其中p1最終指向倒數(shù)第2個完整塊，p2最終指向倒數(shù)第1個完整塊，對于第一種情況，p1指向5，p2指向10，這時可以使p1向后移動（k - mod）個結(jié)點(diǎn)即可（從5移動3個正好是8）。而對于第二種情況，p1指向8，p2指向12，而mod=0，這時的結(jié)果仍然是mod+1，也就是p1向后移動1個結(jié)點(diǎn)就是所求的結(jié)果。 為了滿足（k=結(jié)點(diǎn)數(shù)）的情況，需要將p1的初始值設(shè)為頭結(jié)點(diǎn)，這樣如果（k=結(jié)點(diǎn)數(shù)），就直接從頭結(jié)點(diǎn)向后移動一個結(jié)點(diǎn)就是最后的結(jié)果，如上面的例子求倒數(shù)第12個結(jié)點(diǎn)，也就是求正數(shù)第1個結(jié)點(diǎn)。

下面是這個算法的具體實(shí)現(xiàn)（包括核心算法、生成鏈表及調(diào)用核心算法的代碼）：

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;  //  表示結(jié)點(diǎn)數(shù)  
        while (p.nextNode != null)  
        {  
            p = p.nextNode;  
            count++;  
            //  遇到k的整數(shù)位個結(jié)點(diǎn)，進(jìn)行分塊  
            if (count % k == 0)   
            {                  
                if (p2 != null)  
                    p1 = p2;  
                p2 = p;  
            }  
        }  
        //  k超過鏈表結(jié)點(diǎn)數(shù)，未找到，返回0  
        // 此處也可以用k > count來判斷  
        if (p2 == null)    
        {  
            return 0;  
        }  
        else 
        {  
            int mod = count % k;  
            int offset = mod + 1;  // 任何情況下，最終結(jié)果都是p1指向的結(jié)點(diǎn)向后移動(mod + 1)個結(jié)點(diǎn)  
            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  
    {  
        //產(chǎn)生一個包含1個頭結(jié)點(diǎn)和120個結(jié)點(diǎn)的鏈表  
        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;  
        //  開始查找倒數(shù)第k個結(jié)點(diǎn)，如果找到，返回1，并輸出結(jié)點(diǎn)的data值  
        System.out.println(findNode(headNode, 12));  
    }  
} 

上面程序的輸出結(jié)果如下：

109
1

【編輯推薦】

1. Java筆試題：Java基礎(chǔ)概念（附答案）
2. Java中消除實(shí)現(xiàn)繼承和面向接口編程
3. Red Hat CEO呼吁甲骨文繼續(xù)保持Java開放
4. 自學(xué)Javabean迅速成為Java高手
5. Java通過JNI調(diào)用C語言的方法