[数据结构与算法]数据结构算法每日一练（九）查找链表倒数元素

数据结构算法每日一练（九）查找链表倒数元素

难度： ??

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

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

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

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

（1）基本思想： 如果设计一个尽可能高效的算法，则需要遍历一遍链表便找到链表中倒数第k个位置上的结点，可以定义两个指针变量p和q，初始时，均指向链表的第一个结点，开始遍历时，p指针先沿链表移动，当p指针移动到第k个结点时，q指针开始与p指针同步移动，当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。（如果遍历链表两遍也可以实现，但不是最优算法，即先遍历一遍得到链表结点数量n，然后再遍历n-k次即可实现）

（2）实现步骤

① 设置count计数，count=0，p和q指向头指针的下一个结点。

② 若p为空，则转⑤。

③ 若count = k，则 q指向下一个结点 （q=q->next）；否则，count = count+1。

④ p指向下一个结点（p=p->next），转②。

⑤ 若count = k，则查找成功，输出该结点的data域值，返回1；否则，k值超过链表长度，查找失败，返回0。

⑥ 算法结束。

（3）算法实现

typedef int ElemType; //链表数据的类型定义
typedef struct LNode{
    ElemType data; //结点数据
    struct LNode *next; //结点链接指针
}LNode, *LinkedList;

/*
 * @param LinkedList list 单链表头指针
 * @param int k 查找的位置 
 */
int Search(LinkedList list, int k) {
    LNode *p = list->next, *q = list->next; //指针p，q指示第一个结点
    int count = 0; //位置计数
    while(p != NULL) {
        if(count < k) //计数，如果count<k, 只移动p
            count++;
        else
            q = q->next; //否则，p，q同步移动
    	p = p->next; // p移动
    }//while
    if(count < k)
        return 0; //查找失败，返回0
    else {
        cout << q->data << endl; //查找成功，输出数据
        return 1; //返回1
    }
}