算法习题---线性表之单链表的查找
2021-07-09 02:18
标签：str 输出 height 假设 bsp printf png class list 算法习题---线性表之单链表的查找 标签：str 输出 height 假设 bsp printf png class list 原文地址：https://www.cnblogs.com/ssyfj/p/9568628.html一：问题
已知一个带头结点的单链表，结点结构为（data，link）假设该链表只给出了头指针list，
在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数），
若查找成功，算法输出该结点的data域的值，并返回1，
否则，只返回0。注意：
这里的链表中没有给出链表长度哟
二：思路
设置两个指针p、q，分别指向该链表的第一个元素（头结点的下一个元素）和头结点，一个整数num（初值为1），
p向后移动一个位置num值加1，如果num值大于k，则p，q一起移动，p移动到表尾，q指针指的就是倒数第k个位置上的结点。
如果链表结束，q一直是指向头结点，那么该结点不存在。三：代码实现
Status findElem(LinkList L, int k)
{
LinkList q, p;
p = L->next; //指向第一个
q = L;
int num = 1;
while (p!=NULL)
{
p = p->next;
num++;
if (num > k)
q = q->next;
}
if (q == L)
return ERROR;
printf("%d", q->data);
return OK;
}