lesson 14.2 单链表中寻找第k个倒数节点
发布时间
阅读量：
阅读量
题目描述：
给定一个包含表头节点的单链表，其节点结构为（data，link），假定该链表仅提供头指针list。在不改变链表原有结构的前提下，请设计一个效率尽可能高的算法，用于定位链表中倒数第k个位置的节点。若查找成功，算法需输出该节点data域的值，并返回1；若查找失败，则仅返回0。
思路：
设定两个指针p和q，其中指针p用于遍历整个链表，而指针q初始时指向链表的第一个元素；
当p向前移动k-1次后，q开始同步移动。当p到达链表末尾时，此时q所指向的节点即为倒数第k个节点。
代码：
int getNode(LNode *list,int k){
if(k<1||list==NULL)
return 0;
LNode *p=list->link;
LNode *q=p;
for(int i=1;i<k;i++){ //p走K-1步
p=p->link;
}
if(p==NULL)//k太大了
return 0;
while(p){
q=q->link;
p=p->link;
}
cout<<q->data<<endl;
return 1;全部评论 (0)
还没有任何评论哟~