本文為原創(chuàng)，如需轉(zhuǎn)載，請(qǐng)注明作者和出處，謝謝！

雖然研究生已畢業(yè)，但看到有一些難度的研究生考試題還是忍不住要做做，本文給出了09年研究生入學(xué)考試的一道數(shù)據(jù)結(jié)構(gòu)題的Java實(shí)現(xiàn)。該題的描述如下圖所示。



該題的兩種實(shí)現(xiàn)一位朋友已經(jīng)完成了，詳見(jiàn) 遞歸和非遞歸實(shí)現(xiàn) 。在本文將給出另外一種算法，該算法的空間復(fù)雜度為O(1)，時(shí)間復(fù)雜度為O(n)。這在空間復(fù)雜度和時(shí)間復(fù)雜度上應(yīng)該是比較優(yōu)化了。
本算法的基本思想如下：
既然是查找倒數(shù)第K個(gè)結(jié)點(diǎn)（注意，不是正數(shù)，否則就沒(méi)什么可討論的了），而且鏈表是單向的，還不能改變表結(jié)構(gòu)，這就意味著只能從前往后掃描結(jié)點(diǎn)。我們首先 要知道這個(gè)鏈表有多少個(gè)結(jié)點(diǎn)（如果總結(jié)點(diǎn)數(shù)都不知道，何談倒數(shù)？），這個(gè)非常簡(jiǎn)單，只要從頭掃描一下鏈表，再計(jì)一下數(shù)即可。
在同一時(shí)間從事多項(xiàng)工作會(huì)大大提升效率，當(dāng)然，掃描鏈表也不例外，在掃描鏈表的同時(shí)，還需要做一些其他的工作。既然只能從前向后掃描鏈表，而且要求倒數(shù)第 K個(gè)結(jié)點(diǎn)，那就讓我們把這個(gè)鏈表按長(zhǎng)度為K分成若干塊，而最后掃描的結(jié)果要么結(jié)點(diǎn)數(shù)是K的整數(shù)倍（模為0），要么余數(shù)（模）不為0（多出幾個(gè)結(jié)點(diǎn)，多出的 結(jié)點(diǎn)數(shù)小于K）。
先看看第二種情況。
假設(shè)有12個(gè)結(jié)點(diǎn)的鏈表，每一個(gè)結(jié)點(diǎn)的值從前往后分別是1至12，如下所示：

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

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

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

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

注意，不是物理分，而是使用變量來(lái)保存區(qū)域的邊界（也就是區(qū)域最后一個(gè)結(jié)點(diǎn)的對(duì)象）。
從上面的分隔可以看出，最后剩下兩個(gè)結(jié)點(diǎn)，既然是求倒數(shù)第5個(gè)，而最后剩下了兩個(gè)，那么還缺5-2=3個(gè)，因此，只需要從倒數(shù)第二個(gè)塊（6 7 8 9 10）略過(guò)前兩個(gè)，第三個(gè)結(jié)點(diǎn)（8）就是我們要求的結(jié)果，而5就是題中的k，2就是結(jié)點(diǎn)數(shù)與k的模，因此，可以推出一個(gè)公式，倒數(shù)第k個(gè)結(jié)點(diǎn)就是按長(zhǎng)度為 k按分成的若干塊中的第二塊的第(結(jié)點(diǎn)數(shù) % k+ 1)個(gè)結(jié)點(diǎn)。
下面來(lái)看看(結(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

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

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

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

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

109
1

讀者也可以使用其他的測(cè)試用例來(lái)測(cè)試上面的程序。

本算法從空間復(fù)雜度O(1)和時(shí)間復(fù)雜度O(n)的綜合指標(biāo)基本上算是比較優(yōu)化了，如果哪位讀者還有更簡(jiǎn)單和快速的算法，請(qǐng)跟貼！！

09考研數(shù)據(jù)結(jié)構(gòu)試題的一種解法（Java版）