輸入一個鏈表，輸出該鏈表中倒數(shù)第k個節(jié)點。為了符合大多數(shù)人的習慣，本題從1開始計數(shù)，即鏈表的尾節(jié)點是倒數(shù)第1個節(jié)點。

例如，一個鏈表有 6 個節(jié)點，從頭節(jié)點開始，它們的值依次是 1、2、3、4、5、6。這個鏈表的倒數(shù)第 3 個節(jié)點是值為 4 的節(jié)點。

示例

• 給定一個鏈表: 1->2->3->4->5, 和 k = 2

• 返回鏈表 4->5

方法一：順序查找

以示例為例，鏈表的長度為 5（即：n），倒數(shù)第 2（即：k） 個節(jié)點即為 正數(shù) 第 3（即：n - k） 個節(jié)點，只需要 順序遍歷 到鏈表的第 3（即：n - k）個節(jié)點即為倒數(shù)第 2 （即：k）個節(jié)點。

代碼如下：

復雜度分析

• 時間復雜度：O(n)，其中 n 為鏈表的長度。需要兩次遍歷。

• 空間復雜度：O(1)。

方法二：快慢雙指針

以示例為例，我們將第一個指針 fast 指向鏈表的第 3（即：k + 1） 個節(jié)點，第二個指針 slow 指向鏈表的第 1 個節(jié)點，此時指針 fast 與 slow 二者之間剛好間隔 2 (即：k) 個節(jié)點。此時兩個指針同步向后走，當?shù)谝粋€指針 fast 走到鏈表的尾部空節(jié)點時，則 此時 slow 指針剛好指向鏈表的倒數(shù)第 2（即：k） 個節(jié)點。

代碼如下：

復雜度分析

• 時間復雜度：O(n)，其中 n 為鏈表的長度。我們使用快慢指針，只需要一次遍歷即可，復雜度為 O(n)。

• 空間復雜度：O(1)。

END

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強！

好兄弟可以點贊并關注我的公眾號“javaAnswer”，全部都是干貨。