(15分)已知一个带有表头结点的单链表，结点结构为：

|data|link|

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

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

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

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

[tag_link]

1）算法的基本设计思想： 问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第 k 个结点的位置。算法的基本设计思想：定义两个指针变量 p 和 q，初始时均指向头结点的下一个结点（链表的第一个结点）。p 指针沿链表移动，当 p 指针移动到第 k 个结点时，q 指针开始与 p 指针同步移动；当 p 指针移动到最后一个结点时，q 指针所指示结点为倒数第 k 个结点。以上过程对链表仅进行一遍扫描。

2）算法的详细实现步骤： count=0，p 和 q 指向链表表头结点的下一个结点； 若 p 为空，转 5； 若 count 等于 k，则 q 指向下一个结点；否则，count=count+l; p 指向下一个结点，转 2： 若 count 等于 k，则查找成功，输出该结点的 data 域的值，返回 1；否则，说明 k 值超过了线性表的长度，查找失败，返回 0； 算法结束。

3）算法实现

int FindElement(Node *head, int k)
{
    Node *p1 = head;
    Node *p2 = head;
    for (int i = 0; i < k; i++)
    {
        p1 = p1->link;
        if (p1 == NULL)
        {
            return 0;
        }
    }

    while (p1 != NULL)
    {
        p1 = p1->link;
        p2 = p2->link;
    }
    printf("%d\n", p2->data);
    return 1;
}

提示：算法程序题，如果能够写出数据结构类型定义，正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。 【评分说明】① 若所给出的算法采用一遍扫描方式就能得到止确结果，可给满分 15 分：若采用两遍或多遍扫描才能得到正确结果的，最高给 10 分；若采用递归算法得到正确结果的，最高给 10 分；若实现算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分；若实现的算法的空间复杂度过高（使用了大小与 k 有关的辅助数组），但结果正确，最高给 10 分。 ②若在算法基本思想描述和算法步骤描述中因文学表达没有非常清晰地反映出算法的思路，但在算法实现中能够清晰看出算法思想和步骤且正确，按照 () 的标准给分。 ③若考生的答案中算法基本思想描述、算法步骤描述或算法实现中部分正确，可酌情给分。