参考资料：
[1]剑指OFFER课本 P135
关键词：
第n-k+1个节点、先走再一起走
常规解法：
先走完一遍，再走
高级解法（背住）：
倒数第1个节点，两个指针差0，先走0步，然后一起走
倒数第2个节点，两个指针差1，先走1步，然后一起走
倒数第3个节点，两个指针差2，先走2步，然后一起走
自己的解法：
改进版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if (pListHead == nullptr)
return nullptr;
ListNode* pNode = pListHead;
int nLen=0;
//步骤1：先看链表有几个节点
while (pNode != nullptr)
{
nLen++;
pNode = pNode->next;
}
if (nLen < k)
return nullptr;
//步骤2：从头到尾找到该节点
int nIndexForward = nLen - k;
pNode = pListHead;
while (nIndexForward--)
{
pNode = pNode->next;
}
return pNode;
}
};
初始版：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
//思路：
//思路1：长度为n的链表，倒数第一个节点是n,倒数第二个节点是n-1,所以倒数第k个节点是n-k+1
//思路2：定义两个指针，倒数第一个节点，两个指针差0，两个指针一起走。倒数第二个节点，两个指针差1，两个指针一起走
//所以倒数第k个节点，两个指针差k-1,然后一起走.
//思路1
//步骤1：统计链表的长度
ListNode* pNode = pListHead;
int len=0;
while(pNode!=nullptr)
{
pNode = pNode->next;
len++;
}
//异常情况得写上
if(pListHead == nullptr||len<k)
return nullptr;
//步骤2：输出倒数第K个节点
//不确定，拿个实例来说话，比如1 2 倒数第1个节点，第2-1+1个节点，循环执行1次
pNode = pListHead;//记得弄起点！！！
for(int i=1;i<(len-k+1);i++)
{
pNode = pNode->next;
}
return pNode;
/*
//思路2：
//步骤1:定义2个指针
ListNode* pNode1 = pListHead;
ListNode* pNode2 = pListHead;
if(pNode1 == nullptr)
return nullptr;
//步骤2：倒数第1个节点。先走1步，倒数第2个节点，先走2步，倒数第k个节点，先走k步。XXXXX错误的思路
//怎么把len给考虑进去啊
//倒数第1个节点，两个指针差0，不用先走。倒数第2个节点，两个指针差1，1个指针先走一步。背住！！！！！！给实例验证。比如1
for(int i=1;i<=k-1;i++)
{
pNode1 = pNode1->next;
if(pNode1 == nullptr)
return nullptr;
}
//步骤2:2个指针一起走
while(pNode1->next != nullptr)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode2;
*/
}
};
标准答案：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
//创建2个指针
ListNode* pList1;
ListNode* pList2;
pList1 = pListHead;
pList2 = pListHead;
if(pListHead ==nullptr || k ==0)
return nullptr;
//k=1的时候不执行
//2个指针，访问导数第一个指针，两个指针差0,访问倒数第2个指针，两个指针差1
//1.
for(int i = 1;i<=k-1;i++)
{
pList1 = pList1->next;
//如果pList1指向的为空，返回
if(pList1 == nullptr)
return nullptr;
}
//2.两个指针一起访问
while(pList1->next != nullptr)
{
pList1 = pList1->next;
pList2 = pList2->next;
}
return pList2;
}
};
