題目
輸入一個鏈表咧栗，輸出該鏈表中倒數(shù)第k個節(jié)點。
為了符合大多數(shù)人的習(xí)慣虱肄，本題從1開始計數(shù)致板，即鏈表的尾節(jié)點是倒數(shù)第1個節(jié)點。例如咏窿，一個鏈表有6個節(jié)點斟或，從頭節(jié)點開始，它們的值依次是1集嵌、2萝挤、3、4根欧、5怜珍、6.這個鏈表的倒數(shù)第3個節(jié)點是值為4的節(jié)點。
分析
- 思路1
假設(shè)整個鏈表有n個節(jié)點咽块，那么倒數(shù)第k個節(jié)點就是從頭節(jié)點開始的第n-k+1個節(jié)點绘面。如果我們能夠得到鏈表中節(jié)點的個數(shù)n，那么只要從頭節(jié)點開始往后走n-k+1步就可以了侈沪。
如何得到節(jié)點數(shù)n?這個不難揭璃，只需要從頭開始遍歷鏈表，每經(jīng)過一個節(jié)點亭罪，計數(shù)器加1就行了瘦馍。也就是說為我們需要遍歷鏈表兩次，第一次統(tǒng)計出鏈表中節(jié)點的個數(shù)应役，第二次就能找到倒數(shù)第k個節(jié)點情组。功能可以實現(xiàn)，但是效果不佳
- 思路2
實現(xiàn)只遍歷鏈表一次就能找到倒數(shù)第k個節(jié)點箩祥，我們可以定義兩個指針院崇。第一個指針從鏈表的頭指針開始遍歷向前走k-1步，第二個指針保持不動袍祖；從第k步開始底瓣，第二個指針也開始從鏈表的頭指針開始遍歷，由于兩個指針距離保持在k-1蕉陋，當(dāng)?shù)谝粋€指針（走在前面的）到達(dá)鏈表的尾節(jié)點時捐凭，第二個（走在后面）指針正好指向倒數(shù)第k個節(jié)點
具體分析
下面以有6個節(jié)點的鏈表中找倒數(shù)第3個節(jié)點拨扶。
- 首先用第一個指針從頭結(jié)點開始向前走（2=3-1）步到達(dá)第3個結(jié)點，如下圖(a)所示茁肠。
- 接著把第二個指針初始化指向鏈表的第一個結(jié)點患民，如下圖(b)所示
- 最后讓兩個指針同時向前遍歷，當(dāng)?shù)谝粋€指針到達(dá)鏈表的尾結(jié)點時垦梆，第二個指針指向的剛好是倒數(shù)第3個結(jié)點匹颤，如下圖(c)所示
算法實現(xiàn)
struct ListNode
{
int value;
ListNode *next;
};
ListNode* FindKthToTail(ListNode *listHead, unsigned int k)
{
ListNode *head = listHead;
ListNode *behind = nullptr;
// 第一個指針移動k-1個位置
for (unsigned int i = 0; i < k - 1; i++) {
head = head->next;
}
// 將第二個指針設(shè)置為頭指針
behind = listHead;
// 移動第一個指針一直到尾結(jié)點
while (head->next != nullptr) {
head = head->next;
behind = behind->next;
}
return behind;
}
看起來實現(xiàn)沒有問題，但是程序很容易奔潰
- 輸入的
listHead為空指針奶赔。由于代碼會試圖訪問空指針指向的內(nèi)存惋嚎，從而造成程序奔潰 - 輸入的以
listHead為頭結(jié)點的鏈表的結(jié)點的總數(shù)少于k。由于for循環(huán)中會在鏈表上向前走k-1步站刑，仍然會由于空指針而造成程序的奔潰 - 輸入?yún)?shù)k為0另伍，由于k是一個無符號整數(shù)，那么在
for循環(huán)中k-1得到的將不是-1绞旅，而是4294967295（無符號的oxffffffff）摆尝。因此，for循環(huán)執(zhí)行的次數(shù)遠(yuǎn)遠(yuǎn)超出我們的預(yù)計因悲，同樣會造成程序的奔潰
因此堕汞，一定要注意代碼的容錯處理，保持代碼的健壯性晃琳。針對上面3個問題讯检，分別處理。
- 如果輸入的鏈表頭指針為
nullptr卫旱，那么整個鏈表為空人灼，此時查找倒數(shù)第k個結(jié)點自然應(yīng)該返回 -
nullptr。如果輸入的k為0顾翼，也就是試圖查找倒數(shù)第0個結(jié)點投放，由于我們計算是從1開始，因此輸入0沒有實際意義适贸，也可以返回nullptr - 如果鏈表的結(jié)點數(shù)少于
k灸芳，那么for循環(huán)中遍歷鏈表可能會出現(xiàn)指向nullptr的next，因此在for循環(huán)中加一個if判斷
ListNode* FindKthToTail(ListNode *listHead, unsigned int k)
{
if (listHead == nullptr || k == 0)
return nullptr;
ListNode *head = listHead;
ListNode *behind = nullptr;
// 第一個指針移動k-1個位置
for (unsigned int i = 0; i < k - 1; i++) {
if (head->next != nullptr)
{
head = head->next;
}
else {
return nullptr;
}
}
// 將第二個指針設(shè)置為頭指針
behind = listHead;
// 移動第一個指針一直到尾結(jié)點
while (head->next != nullptr) {
head = head->next;
behind = behind->next;
}
return behind;
}
參考
《劍指offer》
