【题目】
42.(15分)已知一个带有表头结点的单链表，结点结构为 data link，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k 个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则， 只返回0。要求：
(1)描述算法的基本设计思想; (2)描述算法的详细实现步骤;
(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C、C++或Java语言实现)，关键之处请给出简要注释。
【答案要点】
(1) 算法的基本设计思想：
定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动;当p 指针移动到第k个结点时，q指针开始与p指针同步移动;当p指针移动到链表最后一个结点时， q指针所指元素为倒数第k个结点。
以上过程对链表仅进行一遍扫描。
(2) 算法的详细实现步骤：
①count=0，p和q指向链表表头结点的下一个结点;
②若p为空，转⑤;
③若count等于k，则q指向下一个结点;否则，count=count+1;
④p指向下一个结点，转步骤②;
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1;否则，查找失败，返回0：
⑥算法结束。
(3) 算 法 实 现 ： typedef struct LNode{ int data：
struct LNode*link;
}*LinkList;
int SearchN(LinkList list，int k){
LinkList p，q;
int count=0： /*计数器赋初值*/
p=q=list->link; /*p和q指向链表表头结点的下一个结点*/ while(p!=NULL){
if(count
else q=q->link; /*q移到下一个结点*/ p=p->link; /*p移到下一个结点*/
}
if(countdata);/*查找成功*/
return(1);
}
}