輸出單鏈表中倒數(shù)第k個結(jié)點

題目：輸入帶頭結(jié)點的單鏈表L，輸出該單鏈表中倒數(shù)第k個結(jié)點。單鏈表的倒數(shù)第0個結(jié)點為該單鏈表的尾指針。要求只能遍歷1次單鏈表。

解題思路：
如果不要求只能遍歷1次單鏈表，我們可以先遍歷1次單鏈表，求出它的結(jié)點的總個數(shù)n（包括頭結(jié)點），所以單鏈表的結(jié)點是從倒數(shù)第n⑴個到倒數(shù)第0個，然后再遍歷1次單鏈表，遍用時訪問的第n-k⑴個結(jié)點就是該單鏈表中倒數(shù)第k個結(jié)點?，F(xiàn)在要求只能遍歷1次單鏈表，可以設(shè)兩個指針p和q，最開始時它們都指向頭結(jié)點，然后p向后移動k位，最后p,q同時向后移動直到p為最后1個結(jié)點，那末此時q即為所求。

ADT定義以下
#define ElemType int
typedef struct LNode{
    ElemType data;
    LNode *next;
}LNode,*LinkList;

算法實現(xiàn)：

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈