第1章第2节练习题10 查找指定倒数结点

## 问题描述 > 已知一个带有头结点的单链表，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第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 #include 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"); } ~~~