1、题目描述
输入一个链表，输出该链表中倒数第k个结点。
注意：
k >= 0;
如果k大于链表长度，则返回 NULL;
样例
输入：链表：1->2->3->4->5 ，k=2
输出：4
2、问题描述：
3、问题关键：
- 这题还是比较简单的，没有让返回删除第k个结点的链表，不用考虑是否是头结点。
- 如果额外的空间的话，可以用一个数组存起来。
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：先求链表的长度，再求倒数第k个结点。
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;
}
};
