问答题已知一个带有表头结点的单链表，结点结构为(data，link)，假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)，若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0，要求：(1)描述算法的基本设计思想；(2)描述算法的详细实现步骤；(3)根据设计思想和实现步骤，采用程序设计语言描述算法(使用C或C++或Java语言实现)，关键之处请给出简要注释。【2009年全国试题42(15分)】

【正确答案】正确答案：“倒数”和“正数”是相对概念。如战士站队报数从1到10，排头1若从反向报数则是10。本题设指针q指向链表，指针p指向链表第一元素，q是p的前驱(广义)。p向后移动七个结点后，p和q相距k之后同步移动指针p和q，到p=nuU时，q指向倒数第k个结点。另一算法是链表结点依次入栈，入栈完毕退栈，弹出第k个结点，不如前者性能好。算法的主要语句段如下： while(p&&i1ink； ) ／／指针p指向链表第k个结点，i初值为1 if(p==null) {printf(“不存在＼n”)；return 0； ) ／／所给k太大 while(p) {q=q一>link；p=p一>link； } ／／向链表尾同步移动指针p和q return 1；／／q指向倒数第k个结点

【答案解析】