題目：輸入一個(gè)單向鏈表（只有指向下一個(gè)結(jié)點(diǎn)指針），輸出鏈表中的倒數(shù)第k個(gè)結(jié)點(diǎn)。

分析：

1. 一個(gè)單向鏈表只有指向下一個(gè)結(jié)點(diǎn)的指針，所以我們無法得到前面一個(gè)結(jié)點(diǎn)的指針，所以不能通過最樸素的枚舉法來求出。

2. 現(xiàn)在要求出倒數(shù)第k個(gè)結(jié)點(diǎn)。現(xiàn)在用一個(gè)指針枚舉是無法求出，但是我們可以使用兩個(gè)指針法（非常重要）。

? ?初始化設(shè)置兩個(gè)指針p1和p2，p1和p2都指向鏈表的頭結(jié)點(diǎn)。我們可以先讓指針p1指針先走到第k個(gè)結(jié)點(diǎn)，下一步開始兩個(gè)指針p1和p2一起走，當(dāng)p1指向鏈表最后一個(gè)結(jié)點(diǎn)的時(shí)候p2指向即為倒數(shù)第k個(gè)結(jié)點(diǎn)。

? ?為什么呢這個(gè)方法是正確的？

? ?當(dāng)p1指向第k個(gè)結(jié)點(diǎn)的時(shí)候，p2和p1相差k個(gè)結(jié)點(diǎn)，所以當(dāng)p1指向尾結(jié)點(diǎn)的時(shí)候，p2指向的即為倒數(shù)第k個(gè)結(jié)點(diǎn)。

代碼：

[cpp]?view plaincopy

//鏈表結(jié)點(diǎn)??

struct?ListNode{??

????int?value;??

????ListNode?*nextNode;??

};???

??

//求倒數(shù)第k個(gè)結(jié)點(diǎn)??

ListNode*?GetKthFromTail(ListNode?*headNode,?int?k){??

????//數(shù)據(jù)不合法??

????if((headNode?==?NULL)?||?(k?<=?0)){??

????????return?NULL;??

????}???

????ListNode?*p1?=?headNode;??

????ListNode?*p2?=?headNode;??

????int?count?=?1;??

????//讓p1先走到第k個(gè)結(jié)點(diǎn)??

????while((count?<?k)?&&?(p1?!=?NULL)){??

????????p1?=?p1->nextNode;??

????????++count;??

????}???

????//判斷數(shù)據(jù)合法性??

????if(p1?==?NULL){??

????????return?NULL;??

????}???

????//兩個(gè)指針一起走，當(dāng)p1指向尾結(jié)點(diǎn)是p2指向即為倒數(shù)第k個(gè)結(jié)點(diǎn)???

????while(((p1->nextNode)?!=?NULL)){??

????????p1?=?p1->nextNode;??

????????p2?=?p2->nextNode;??

????}??

????return?p2;??

}???

總結(jié)

以上是生活随笔為你收集整理的求链表倒数第k个结点的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。