走的最慢的人怎憋，只要他不喪失目標(biāo)纽疟，也比漫無(wú)目的徘徊的人走得快罐韩。- 萊辛
輸入一個(gè)鏈表，輸出該鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)污朽。為了符合大多數(shù)人的習(xí)慣散吵，本題從1開(kāi)始計(jì)數(shù)，即鏈表的尾節(jié)點(diǎn)是倒數(shù)第1個(gè)節(jié)點(diǎn)蟆肆。例如矾睦，一個(gè)鏈表有6個(gè)節(jié)點(diǎn)，從頭節(jié)點(diǎn)開(kāi)始炎功，它們的值依次是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.
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
解題思路
一提到鏈表，好多題目都可以有幾種相似的解法更啄，但最好本著時(shí)間復(fù)雜度是O(N)的思路稚疹，即遍歷鏈表一邊即可，太多了祭务，估計(jì)面試官不會(huì)認(rèn)可内狗。除了用空間換時(shí)間的想法，比如多開(kāi)辟出一個(gè)數(shù)組來(lái)記錄鏈表义锥，還有但指針柳沙，大家都普遍認(rèn)可的解法就是雙指針?lè)ǎ步锌炻羔樂(lè)ò璞丁１绢}為例：
生成兩個(gè)指針從頭節(jié)點(diǎn)開(kāi)始赂鲤，快指針先走k-1步，然后快慢指針同時(shí)向后贰拿，當(dāng)快指針到達(dá)鏈表末尾的時(shí)候，慢指針正好處于第k個(gè)節(jié)點(diǎn)熄云。代碼也是相當(dāng)?shù)暮?jiǎn)單膨更，討論下時(shí)間復(fù)雜度，快指針走了O(N), 慢指針走了O(N-K),時(shí)間復(fù)雜度為 O(N), 空間復(fù)雜度為 O(1), 只有兩個(gè)指針缴允。
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head, fast = head;
for(int i =0; i< k -1; i++){
if(fast.next == null)
return null;
fast = fast.next;
}
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
return slow;
}
相似的題型還有很多
876. 鏈表的中間結(jié)點(diǎn) - 快指針是慢指針的兩倍步長(zhǎng)
