1.5 如何找出單鏈表中的倒數(shù)第k個(gè)元素

【出自WR筆試題】

難度系數(shù)：★★★☆☆

被考察系數(shù)：★★★★★

題目描述：

找出單鏈表中的倒數(shù)第k個(gè)元素，如給定單鏈表：1→2→3→4→5→6→7，則單鏈表的倒數(shù)第k=3個(gè)元素為5。

分析與解答：

方法一：順序遍歷兩遍法

主要思路：首先遍歷一遍單鏈表，求出整個(gè)單鏈表的長度n，然后把求倒數(shù)第k 個(gè)元素轉(zhuǎn)換為求順數(shù)第n-k個(gè)元素，再去遍歷一次單鏈表就可以得到結(jié)果。但是該方法需要對單鏈表進(jìn)行兩次遍歷。

方法二：快慢指針法

由于單鏈表只能從頭到尾依次訪問鏈表的各個(gè)結(jié)點(diǎn)，因此如果要找單鏈表的倒數(shù)第k 個(gè)元素，也只能從頭到尾進(jìn)行遍歷查找。在查找過程中，設(shè)置兩個(gè)指針，讓其中一個(gè)指針比另外一個(gè)指針先前移k步，然后兩個(gè)指針同時(shí)往前移動。循環(huán)直到先行的指針值為null時(shí)，另一個(gè)指針?biāo)傅奈恢镁褪撬业奈恢谩３绦虼a如下：

程序的運(yùn)行結(jié)果為

算法性能分析：

這種方法只需要對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O（N）。另外，由于只需要常量個(gè)指針變量來保存結(jié)點(diǎn)的地址信息，因此，空間復(fù)雜度為O（1）。

引申：如何將單鏈表向右旋轉(zhuǎn)k個(gè)位置。

題目描述：給定單鏈表1→2→3→4→5→6→7，k=3，那么旋轉(zhuǎn)后的單鏈表變?yōu)?→6→7→1→2→3→4。

分析與解答：

主要思路為：①首先找到鏈表倒數(shù)第k+1個(gè)結(jié)點(diǎn)slow和尾結(jié)點(diǎn)fast（如下圖所示）；②把鏈表斷開為兩個(gè)子鏈表，其中后半部分子鏈表結(jié)點(diǎn)的個(gè)數(shù)為k；③使原鏈表的尾結(jié)點(diǎn)指向鏈表的第一個(gè)結(jié)點(diǎn)；④使鏈表的頭結(jié)點(diǎn)指向原鏈表倒數(shù)第k個(gè)結(jié)點(diǎn)。

實(shí)現(xiàn)代碼如下：

程序的運(yùn)行結(jié)果為

算法性能分析：

這種方法只需要對鏈表進(jìn)行一次遍歷，因此，時(shí)間復(fù)雜度為O（n）。另外，由于只需要幾個(gè)指針變量來保存結(jié)點(diǎn)的地址信息，因此，空間復(fù)雜度為O（1）。