## 問題描述 > 已知一個帶有頭結點的單鏈表，在不改變鏈表的前提下，請設計一個盡可能高效的算法，查找鏈表中倒數第k個位置上的結點。若查找成功，算法輸出該結點的data域的值 ## 算法思想 > 倒數第k個位置，很容易想到的算法便是遍歷整條單鏈表，得出單鏈表的長度len，然后再遍歷(len?k)個結點便可以得到倒數第k個位置的結點的數據域。但是這樣實際上就導致鏈表遍歷了兩次，時間復雜度為2×O(n)。 換個思路，使用兩個指針p和q，讓指針q先遍歷k個結點，然后指針p和指針q同時開始遍歷鏈表。當指針q指向表尾結點時，指針p所指的結點便是倒數第k個位置的結點。如此僅遍歷一次便找到了倒數第k個位置上的結點。時間復雜度僅為O(n)。 ## 算法描述 ~~~ LNode* FindReK(LNode *head, int k) { LNode *q=head->next; LNode *p=head->next; while(q){ if(k){ q=q->next; --k; }else{ p=p->next; q=q->next; } } return p; } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); LNode* FindReK(LNode*, int); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=CreatList(head); Print(head); int k=3; LNode *p; p=FindReK(head,k); if(p) printf("The number is %d in the Reverse postion %dth\n",p->data,k); else printf("It not find the number!\n"); return 0; } //頭插法建立單鏈表 LinkList CreatList(LNode *head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //查找倒數第k個結點 LNode* FindReK(LNode *head, int k) { LNode *q=head->next; LNode *p=head->next; while(q){ if(k){ q=q->next; --k; }else{ p=p->next; q=q->next; } } return p; } //打印全部結點 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~