面試題22. 鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)
難度簡(jiǎn)單
輸入一個(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.
第一種思路：
1讯赏、利用雙指針，fast冷尉， slow
2漱挎、將 fast 移動(dòng)到與 slow 相距為 k 的距離的節(jié)點(diǎn)上；
3雀哨、同時(shí)移動(dòng) fast 與 slow磕谅，當(dāng) fast 到達(dá)結(jié)尾指向 null 時(shí)私爷，此時(shí) slow 所指向的節(jié)點(diǎn)就是倒數(shù)第 k 個(gè)節(jié)點(diǎn)，直接返回 slow膊夹。
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null || k <= 0) return head;
ListNode fast = head, slow = head;
for(int i = 0; i < k; i ++)
fast = fast.next;
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
第二種思路
回溯法衬浑。
利用遞歸，直接遞歸到鏈表的尾部放刨，當(dāng)?shù)竭_(dá)尾部 null 時(shí)工秩，開(kāi)始回溯，不斷地將計(jì)數(shù) num 加一。當(dāng)計(jì)數(shù) num 等于 k 時(shí)，此時(shí)也就到達(dá)了鏈表倒數(shù)第 k 個(gè)結(jié)點(diǎn)秸讹，將此節(jié)點(diǎn)賦值給成員變量 result铡俐。
class Solution {
private int num = 0; //從鏈表的尾部開(kāi)始加1
ListNode result = null;
public ListNode getKthFromEnd(ListNode head, int k) {
lookingNode(head, k);
return result;
}
private void lookingNode(ListNode node, int k){
if(node == null)
return ;
// 不斷地遞歸到尾部。
lookingNode(node.next, k);
// 從尾部開(kāi)始計(jì)數(shù)
num ++;
if(num == k)
result = node;
}
}
