本文為原創，如需轉載，請注明作者和出處，謝謝！
雖然研究生已畢業，但看到有一些難度的研究生考試題還是忍不住要做做，本文給出了09年研究生入學考試的一道數據結構題的Java實現。該題的描述如下圖所示。
該題的兩種實現一位朋友已經完成了，詳見
遞歸和非遞歸實現 。在本文將給出另外一種算法，該算法的空間復雜度為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
讀者也可以使用其他的測試用例來測試上面的程序。
本算法從空間復雜度O(1)和時間復雜度O(n)的綜合指標基本上算是比較優化了，如果哪位讀者還有更簡單和快速的算法，請跟貼！！
新浪微博：http://t.sina.com.cn/androidguy 昵稱：李寧_Lining