題目鏈接：鏈表中倒數(shù)第K個(gè)數(shù)
我的思路
- 題目是單向鏈表蚓炬，而且要遍歷一次鏈表就搞定的話，肯定需要一個(gè)指針指向第K個(gè)數(shù)的地址躺屁。
- 若想保證是第K個(gè)數(shù)肯夏，必須當(dāng)時(shí)結(jié)束鏈表遍歷，能確定單向鏈表結(jié)束遍歷的方法就是一個(gè)指針指向最后一個(gè)節(jié)點(diǎn)犀暑。
- 此時(shí)不難發(fā)現(xiàn)這兩個(gè)節(jié)點(diǎn)距離差為K驯击。
- 第一次循環(huán)K次，是領(lǐng)先的指針移動(dòng)到第K個(gè)節(jié)點(diǎn)耐亏，然后在循環(huán)的時(shí)候同時(shí)移動(dòng)兩個(gè)指針相同步速徊都，一定能指向倒數(shù)第K個(gè)數(shù)字
實(shí)現(xià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)
{
//鏈表為空 結(jié)束
if(pListHead==NULL||k==0)
{
return 0;
}
ListNode *pAhead =pListHead;
ListNode *pBehind =NULL;
for(unsigned int i =0;i<k-1;++i)
{
if(pAhead->next!=NULL)
pAhead=pAhead->next;
else
{
return NULL;
}
}
pBehind=pListHead;
while(pAhead->next!=NULL)
{
pAhead=pAhead->next;
pBehind=pBehind->next;
}
return pBehind;
}
};
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
