輸出單鏈表中倒數第k個結點

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

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

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

算法實現：

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈