返回倒数第 k 个节点
题目描述
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
注意：本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2 输出： 4
说明：
给定的 k 保证是有效的。
解法一：快慢指针
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode *fast = head, *slow = head;
for(int i=0;i<k;i++){
fast = fast->next;
}
while(fast != nullptr){
fast = fast->next;
slow = slow->next;
}
return slow->val;
}
};
解法二：递归
传入一个整型的指针或者引用，初始是值为 k，在递归退出的时候将其减 1，当递归退出到倒数第 k 个节点时，其值自然已经减小为 0 了，此时返回当前节点即可。
class Solution {
public:
int kthToLast(ListNode* head, int k) {
ListNode *node = kth_node_to_last(head, k);
return node->val;
}
private:
static ListNode* kth_node_to_last(ListNode* head, int& k){
if(head == nullptr) return nullptr;
ListNode* node = kth_node_to_last(head->next, k);
if(node != nullptr){
return node;
}
k--;
if(k == 0){
return head;
}
return nullptr;
}
};