1.5 如何找出單鏈表中的倒數第k個元素

難度系數：★★★☆☆

被考查系數：★★★★★

題目描述：

找出單鏈表中的倒數第k個元素，例如給定單鏈表：1->2->3->4->5->6->7，則單鏈表的倒數第k=3個元素為5。

分析與解答：

方法一：順序遍歷兩遍法

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

方法二：快慢指針法

由于單鏈表只能從頭到尾依次訪問鏈表的各個結點，因此，如果要找鏈表的倒數第k個元素，也只能從頭到尾進行遍歷查找，在查找過程中，設置兩個指針，讓其中一個指針比另一個指針先前移k步，然后兩個指針同時往前移動。循環直到先行的指針值為null時，另一個指針所指的位置就是所要找的位置。實現代碼如下：

程序的運行結果為

算法性能分析：

這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(n)。另外，由于只需要常量個指針變量來保存結點的地址信息，因此，空間復雜度為O(1)。

引申：如何將單鏈表向右旋轉k個位置？

題目描述：給定單鏈表1->2->3->4->5->6->7，k=3，那么旋轉后的單鏈表變為5->6->7->1->2->3->4。

分析與解答：

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

實現代碼如下：

程序的運行結果為

算法性能分析：

這種方法只需要對鏈表進行一次遍歷，因此，時間復雜度為O(n)。另外，由于只需要幾個指針變量來保存結點的地址信息，因此，空間復雜度為O(1)。