本文共 1593 字，大约阅读时间需要 5 分钟。
已知一个带有表头结点的单链表，结点结构为：
| data | link |
假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：
1）描述算法的基本设计思想。
2）描述算法的详细实现步骤。
3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。
分析：用两次遍历一定能得到结果，第一次计算该链表的长度，第二次找到n-k的位置。这样15分只能得到10分。
最优解是一次遍历。
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
n=9，k=4，倒数第4个元素是6，对应着第6个位置。
p、q相差3个位置（k-1），p移动到第k个位置，q开始移动。
答：
（1）算法思想：设置两个指针变量p和q，初始时均指向头结点的下一个结点，即链表的第一个及诶但。p指针沿着链表移动到第k个位置时，q指针也开始移动。当第一个指针移动到末尾时，第二个指针刚好在倒数第k个位置。完成了一次遍历得到查找结果的目的。p、q指针相差k-1的距离。
（2）实现步骤：
（3）代码：
typedef int ElemType; //链表数据的类型定义，默认链表数据类型是int型 typedef struct LNode{ //链表结点的结构定义 ElemType data; //结点数据 struct LNode *link; // 结点链接指针 //指针名link可以指向任意现有的LNode类型的结构，指针link可以指向每一个结点 };LNode, *LinkList; //单链表的类型定义为LinkList int Search_k(LinkList list, int k) //LinkList类型的list，list指向头结点 { LNode *p=list->link, *q=list->link; //头结点的下一个结点，p、q指向第一个结点 int count = 0; while(p!=NULL){ //这里p、q保持k的间距，p移动的次数就是链表的长度 if(count link; //if条件不满足，p移动k位后，p、q同步移动，保持k的间距 p=p->link; } if(count data); //设定数据域存储类型为int, q->data,用->访问q指向的结点的data变量 return 1; //函数类型为int，查找成功，最后返回一个1 } }
单链表的定义：
typedef int ElemType; //链表数据的类型定义，默认链表数据类型是int型 typedef struct LNode{ //定义一个结构，别名LNode，下次见到LNode就是这种结构 ElemType data; //数据域 struct LNode *link; // 结构指针，指针域，指向下一个结点 //指针名link可以指向任意现有的LNode类型的结构，指针link可以指向每一个结点 };LNode, *LinkList; //单链表的类型定义为LinkList 如果list是Linklist类型的变量，list为单链表的头指针，它指向表中第一个结点。
转载地址：http://aeeii.baihongyu.com/