查找带有头结点的单链表的倒数第k个位置上的结点

问题描述：

已知一个带有表头结点的单链表，结点结构为

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的 data域的值，并返回1；否则，只返回0。要求：

1)描述算法的基本设计思想。

2)描述算法的详细实现步骤。

3)根据设计思想和实现步骤，用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。

问题解答：

1)算法的基本设计思想如下：

问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量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；否则，说明k值超过了线性表的长度，查找失败，返回0。
• ⑥算法结束。

3)算法实现

typedef int ElemType;    //链表数据的类型定义
typedef struct LNode{    //链表结点的结构定义
    ElemType data;    //结点数据
    struct Lnode *link;    //结点链接指针
}LNode, *LinkList;
int Search_k(LinkList list,int k) {
    //查找链表list倒数第k个结点，并输出该结点data域的值
    LNode *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

注意：若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高分为10分。若采用递归算法得到正确结果的，最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。