面試題22. 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
題目描述
輸入一個(gè)鏈表剪菱，輸出該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)栖茉。為了符合大多數(shù)人的習(xí)慣罪裹，本題從1開始計(jì)數(shù)饱普，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個(gè)節(jié)點(diǎn)运挫。例如，一個(gè)鏈表有6個(gè)節(jié)點(diǎn)套耕，從頭節(jié)點(diǎn)開始谁帕，它們的值依次是1、2冯袍、3匈挖、4、5康愤、6儡循。這個(gè)鏈表的倒數(shù)第3個(gè)節(jié)點(diǎn)是值為4的節(jié)點(diǎn)。
示例：
給定一個(gè)鏈表: 1->2->3->4->5, 和 k = 2.
返回鏈表 4->5.
題目分析
這題沒想到很好的方法征冷，只是遍歷了一次鏈表择膝，獲取鏈表的長度，然后獲取第size-k個(gè)節(jié)點(diǎn)检激，時(shí)間復(fù)雜度也還是O（N）肴捉，但是仔細(xì)一想，這樣的題目應(yīng)該不會(huì)出現(xiàn)在劍指Offer里呵扛，然后翻了一下題解每庆，剛好第一個(gè)就是CXX同學(xué)新鮮滾熱辣剛寫出來的，看了標(biāo)題就想起一個(gè)大一的時(shí)候了解過的快慢指針思想（很慚愧大二上修完數(shù)據(jù)結(jié)構(gòu)之后就沒有刷過題了現(xiàn)在什么都不會(huì)了）今穿，然后就開始繼續(xù)馬馬馬...
言歸正傳缤灵，其實(shí)快慢指針法和我那個(gè)“沒那么好的”方法其實(shí)是一樣的，我的第一輪遍歷相當(dāng)于快指針蓝晒，先走到尾部的null腮出，計(jì)算出走出的步數(shù)，然后第二輪遍歷只要走到第一輪遍歷的前k個(gè)節(jié)點(diǎn)就好芝薇，也就是倒數(shù)第k個(gè)節(jié)點(diǎn)胚嘲，而快慢指針做法里的慢指針相當(dāng)于我的第二輪遍歷，因?yàn)槁羔槺瓤熘羔樎浜罅薻步洛二，所以快指針到達(dá)null的時(shí)候馋劈，慢指針剛好走到null的前k個(gè)節(jié)點(diǎn)，也恰恰是倒數(shù)第k個(gè)節(jié)點(diǎn)晾嘶。兩種方法都能得出正確的答案妓雾，時(shí)間復(fù)雜度都是O(N)，都需要走2N-K步垒迂，但是能夠?qū)⒖炻羔樀乃枷腱`活運(yùn)用到題目當(dāng)中械姻，這是CXX牛皮的地方，正如他所說的机断，刷題楷拳，共勉绣夺！
//快慢指針做法
fun getKthFromEnd(head: ListNode?, k: Int): ListNode? {
var fast = head
var slow = head
var n = k
while(n>=1){
n--
fast = fast?.next
}
while(fast!=null){
fast = fast.next
slow = slow?.next
}
return slow
}
//蠻力法
fun getKthFromEndForce(head: ListNode?, k: Int): ListNode? {
var size = 0
var node = head
while(node != null){
size++
node = node.next
}
size-=k
node = head
while(size!=0){
size--
node = node?.next
}
return node
}
