查找单链表倒数第k个结点(遍历一次实现)
一、问题：
已知一个带表头结点的单链表，结点结构为
typedef struct node
{
ElemType data; //数据域
struct node *next; //指针域
}LNode,*LinkList;在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，输出改结点的data域的值。
二、算法思想:
定义两个指针p,q,初始时均指向头结点，p沿链表开始向后移动，当p指向第k个元素结点时，q开始移动，这样当p到达链表尾部时q刚好指向倒数第k个结点。 注意:这样只需要遍历一次链表，考试时直接满分，你如果遍历两次那就要扣分了，时间复杂度是评分的标准。 算法的实现代码如下:
LinkList find_k(LinkList H,int k)//查找单链表中倒数第k个结点(一次遍历实现得满分)
{
LNode *p=H;
LNode *q=H;
int i=0;
while(p->next!=NULL)
{
p=p->next;
i++;
if(i>=k)
{
q=q->next;
}
}
printf("倒数第%d个结点的值为%d\n",k,q->data);
return q;
}三、运行截图:
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-06-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
