1蠕嫁、題目描述
輸入一個(gè)鏈表锨天，輸出該鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)。
注意：
k >= 0;
如果k大于鏈表長(zhǎng)度剃毒，則返回 NULL;
樣例
輸入：鏈表：1->2->3->4->5 病袄，k=2
輸出：4
2搂赋、問(wèn)題描述：
3、問(wèn)題關(guān)鍵：
- 這題還是比較簡(jiǎn)單的益缠，沒(méi)有讓返回刪除第k個(gè)結(jié)點(diǎn)的鏈表脑奠，不用考慮是否是頭結(jié)點(diǎn)。
- 如果額外的空間的話幅慌，可以用一個(gè)數(shù)組存起來(lái)宋欺。
4、C++代碼：
方法1:只遍歷一次胰伍，且不用額外的空間齿诞。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* findKthToTail(ListNode* head, int k) {
ListNode *first = head, *second = head;
while(k -- && first) {
first = first->next;
}
if (k >= 0) return NULL;
else {
while(first) {
first = first->next;
second = second->next;
}
return second;
}
}
};
方法2：先求鏈表的長(zhǎng)度，再求倒數(shù)第k個(gè)結(jié)點(diǎn)骂租。
class Solution {
public:
ListNode *findKthToTail(ListNode *head, int k) {
int n = 0;
for (auto p = head; p; p = p->next) n ++;
if (n < k) return NULL;
auto p = head;
for (int i = 0; i < n - k; i ++) p = p->next;
return p;
}
};
