数据结构
2009-42
已知一个带有表头结点的单链表，结点结构为
[ data | link ]
假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。要求：
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用 C、C++ 或 Java 语言实现），关键之处请给出简要注释。
答案
【答案】
1）算法基本设计思想：
采用双指针法，一次遍历完成查找。设指针 p 和 q ，初始均指向链表第一个结点（头结点之后）。 p 先向前移动 k 步，若提前到达链表末尾则 k 值非法。之后 p 与 q 同时移动，当 p 到达最后一个结点时， q 所指即为倒数第 k 个结点。
2）算法详细实现步骤：
① 初始化指针 p = list → link ， q = list → link ，计数器 count = 0 。
② 当 p 不为空时循环：
- 若 count < k ，则 p = p → link ， count = count + 1 ；
- 否则， p = p → link ， q = q → link 。
③ 循环结束后，若 count = k ，则 q 指向倒数第 k 个结点，输出 q → data 并返回 1；否则（ count < k ）， k 超出链表长度，返回 0。
3）算法实现（C语言）：
typedef struct LNode {
int data;
struct LNode *link;
} *LinkList;
int Search_k(LinkList list, int k) {
LinkList p = list->link, q = list->link; // 初始指向第一个结点
int count = 0;
while (p != NULL) {
if (count < k) { // p先前进k步
p = p->link;
count++;
} else { // 之后p和q同步前进
p = p->link;
q = q->link;
}
}
if (count == k) { // 链表长度≥k
printf("%d", q->data);
return 1;
}
return 0; // k超出链表长度
}