题目
返回倒数第k个结点 leetcode 面试题02.02
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
示例：
输入：1->2->3->4->5和k=2
输出：4
思路
数组/栈 方法
这个方法比较简单，但是会占用额外空间。
如果用数组，迭代的获取链表中的值将其存储在数组中，然后获取倒数第K个结点即可。
如果用栈，迭代的获取链表中的值将其存储在栈中，然后依次出栈k次即可。
时间复杂度O(n)
空间复杂度O(n)
快慢指针法
使用双指针来解决，首先定义快慢指针都在头结点，然后快指针先走k步，然后快慢指针同时走直到快指针走到空结点，此时慢指针即为倒数第k个结点。
解析：
- (slow)(fast)1->2->3->4->5->null slow=fast=1
- (slow)1->2->3(fast)->4->5->null 快指针走两步到3，慢指针仍然在1
- 1->2->3->4(slow)->5->null(fast) 当快指针到达空结点时，慢指针自然在倒数第2个结点4上。
时间复杂度O(n)
空间复杂度O(1)
c++代码
int kthToLast(ListNode* head, int k) {
ListNode *slow=head,*fast=head;
while(k--){
fast = fast->next;
}
while(fast != NULL){
slow = slow->next;
fast = fast->next;
}
return slow->val;
}
python3代码
class Solution:
def kthToLast(self, head: ListNode, k: int) -> int:
fast,slow = head,head
while k != 0:
fast = fast.next
k = k-1
while fast is not None:
fast = fast.next
slow = slow.next
return slow.val
