2020考研计算机备考考点每日一练2019.5.31-线性表（3）

2020考研计算机备考考点每日一练，备考计算机的同学注意了~启航小编每天都会为大家带来计算机考研知识点的分享，以下是今天的知识点练习~更多计算机专业课考研真题及考研资讯尽在启航考研计算机频道。

知识点-线性表

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

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

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

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

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

参考答案：

(1)算法基本思想如下：

从头至尾遍历单链表，并用指针P指向当前节点的前K个节点。当遍历到链表的最后一个节点时，指针P所指向的节点即为所查找的节点。

(2)详细实现步骤：

第一种方法：遍历两遍，求链表长度，再遍历第K个位置——不高效

第二种方法：增加两个指针变量和一个整型变量:

指针P1指向当前遍历的节点;指针P指向P1所指向节点的前K个节点，如果P1之前没有K个节点，那么P指向表头节点。整型变量i表示当前遍历了多少节点， 当i>k时，指针p随着每次遍历，也向前移动一个节点。当遍历完成时，p或者指向表头节点，或者指向链表中倒数第K个位置上的节点。

启航课程推荐>>>>计算机半年集训定向营》》》课时200+、全职老师高校硕博亲授、面授答疑与在线 答疑相结合更有全年复习规划指导，让你在备考过程不再迷茫

详情了解>>>>计算机半年集训定向营