问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想是：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动；当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。
（2）算法的详细实现步骤（5 分）：
① count=0，p 和 q 指向链表表头结点的下一个结点；
② 若 p 为空，转⑤；
③ 若 count 等于 k，则 q 指向下一个结点；否则，count=count+1；
④ p 指向下一个结点，转②；
⑤ 若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0；
⑥ 算法结束。
（3）算法实现（5 分）：
typedef int ElemType;
// 链表数据的类型定义
typedef struct LNode {
// 链表结点的结构定义
ElemType data; // 结点数据
struct LNode *link; // 结点链接指针
} *LinkList;
int Search_k(LinkList list, int k) {
// 查找链表 list 倒数第 k 个结点，并输出该结点 data 域的值
LinkList p = list->link, q = list->link; // 指针 p、q 指示第一个结点
int count = 0;
while (p != NULL) { // 遍历链表直到最后一个结点
if (count < k)
count++; // 计数，若 count < k 只移动 p
else
q = q->link;
p = p->link; // 之后让 p、q 同步移动
} // while
if (count < k)
return 0; // 查找失败返回 0
else { // 否则打印并返回 1
printf("%d", q->data);
return 1;
}
} // Search_k
The road of your choice, you have to go on !
粤ICP备16082171号-1
登录后提交答案