參考資料：
[1]劍指OFFER課本 P135
關(guān)鍵詞：
第n-k+1個(gè)節(jié)點(diǎn)、先走再一起走
常規(guī)解法：
先走完一遍惨好，再走
高級(jí)解法（背谆蛙睢）：
倒數(shù)第1個(gè)節(jié)點(diǎn)，兩個(gè)指針差0日川，先走0步蔓腐，然后一起走
倒數(shù)第2個(gè)節(jié)點(diǎn)，兩個(gè)指針差1龄句，先走1步回论，然后一起走
倒數(shù)第3個(gè)節(jié)點(diǎn)，兩個(gè)指針差2分歇，先走2步傀蓉，然后一起走
自己的解法：
改進(jìn)版：
/*
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：先看鏈表有幾個(gè)節(jié)點(diǎn)
while (pNode != nullptr)
{
nLen++;
pNode = pNode->next;
}
if (nLen < k)
return nullptr;
//步驟2：從頭到尾找到該節(jié)點(diǎn)
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的鏈表，倒數(shù)第一個(gè)節(jié)點(diǎn)是n,倒數(shù)第二個(gè)節(jié)點(diǎn)是n-1,所以倒數(shù)第k個(gè)節(jié)點(diǎn)是n-k+1
//思路2：定義兩個(gè)指針职抡，倒數(shù)第一個(gè)節(jié)點(diǎn)葬燎，兩個(gè)指針差0，兩個(gè)指針一起走繁调。倒數(shù)第二個(gè)節(jié)點(diǎn)萨蚕，兩個(gè)指針差1，兩個(gè)指針一起走
//所以倒數(shù)第k個(gè)節(jié)點(diǎn)蹄胰，兩個(gè)指針差k-1,然后一起走.
//思路1
//步驟1：統(tǒng)計(jì)鏈表的長度
ListNode* pNode = pListHead;
int len=0;
while(pNode!=nullptr)
{
pNode = pNode->next;
len++;
}
//異常情況得寫上
if(pListHead == nullptr||len<k)
return nullptr;
//步驟2：輸出倒數(shù)第K個(gè)節(jié)點(diǎn)
//不確定岳遥，拿個(gè)實(shí)例來說話，比如1 2 倒數(shù)第1個(gè)節(jié)點(diǎn)裕寨，第2-1+1個(gè)節(jié)點(diǎn)浩蓉，循環(huán)執(zhí)行1次
pNode = pListHead;//記得弄起點(diǎn)Ｅ杉獭！捻艳！
for(int i=1;i<(len-k+1);i++)
{
pNode = pNode->next;
}
return pNode;
/*
//思路2：
//步驟1:定義2個(gè)指針
ListNode* pNode1 = pListHead;
ListNode* pNode2 = pListHead;
if(pNode1 == nullptr)
return nullptr;
//步驟2：倒數(shù)第1個(gè)節(jié)點(diǎn)驾窟。先走1步，倒數(shù)第2個(gè)節(jié)點(diǎn)认轨，先走2步绅络，倒數(shù)第k個(gè)節(jié)點(diǎn)，先走k步嘁字。XXXXX錯(cuò)誤的思路
//怎么把len給考慮進(jìn)去啊
//倒數(shù)第1個(gè)節(jié)點(diǎn)恩急，兩個(gè)指針差0，不用先走纪蜒。倒數(shù)第2個(gè)節(jié)點(diǎn)衷恭，兩個(gè)指針差1，1個(gè)指針先走一步纯续。背姿嬷椤！ｂ怼４翱础！Ｍ没辍烤芦！給實(shí)例驗(yàn)證。比如1
for(int i=1;i<=k-1;i++)
{
pNode1 = pNode1->next;
if(pNode1 == nullptr)
return nullptr;
}
//步驟2:2個(gè)指針一起走
while(pNode1->next != nullptr)
{
pNode1 = pNode1->next;
pNode2 = pNode2->next;
}
return pNode2;
*/
}
};
標(biāo)準(zhǔn)答案：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
//創(chuàng)建2個(gè)指針
ListNode* pList1;
ListNode* pList2;
pList1 = pListHead;
pList2 = pListHead;
if(pListHead ==nullptr || k ==0)
return nullptr;
//k=1的時(shí)候不執(zhí)行
//2個(gè)指針析校，訪問導(dǎo)數(shù)第一個(gè)指針构罗，兩個(gè)指針差0,訪問倒數(shù)第2個(gè)指針，兩個(gè)指針差1
//1.
for(int i = 1;i<=k-1;i++)
{
pList1 = pList1->next;
//如果pList1指向的為空智玻，返回
if(pList1 == nullptr)
return nullptr;
}
//2.兩個(gè)指針一起訪問
while(pList1->next != nullptr)
{
pList1 = pList1->next;
pList2 = pList2->next;
}
return pList2;
}
};
