题目
(15分)已知一个带有表头结点的单链表,结点结构为:
假设该链表只给出了头指针list
。在不改变链表的前提下,请设计一个尽可能高效的算法:
查找链表中倒数第 k 个位置上的结点(k 为正整数)。
若查找成功,算法输出该结点的 data
域的值,并返回 1;否则,只返回 0。
要求:
⑴ 描述算法的基本设计思想;
⑵ 描述算法的详细实现步骤;
⑶ 根据设计思想和实现步骤,采用程序设计语言描述算法
注意题目所给信息
1.带头结点
2.单链表:不能访问前继节点,只能访问后继节点。
3.未知单链表长度
4.k为正整数,即k>0。不需要做k<=0越界判断。
单链表
单链表(单向链表)数据结构回顾:
单链表是线性表的链式存储。由多个节点组成,每个节点又由数据域和指针域构成。如图: