题目描述
输入一个链表，输出该链表中倒数第k个结点。
题解：
1、普通解法，先遍历一遍计算链表长度，然后遍历到倒数第k个节点；
2、只遍历一遍，使用双指针，使得头尾指针位差为k，那么当尾指针为空时，头指针就是倒数第k个位置。
//遍历两次，垃圾
class Solution01 {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr || k <= )return nullptr;
int listLenght = ;
ListNode *res = nullptr, *p = pListHead;
while (p != nullptr)
{
listLenght++;
p = p->next;
}
if (listLenght < k)return res;
res = pListHead;
int nums = ;
while (nums < (listLenght - k))
{
res = res->next;
nums++;
}
return res;
}
}; //遍历一次，双指针
class Solution02 {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr || k <= )return nullptr;
ListNode *L, *Lk;
L = Lk = pListHead;
int i = ;
for (; Lk != nullptr; ++i)
{
if (i >= k)
L = L->next;
Lk = Lk->next;
}
if (i < k)return nullptr;
return L;
}
};