题目
解决代码及点评
/*题目：已知单向链表，有n个元素，求倒数第k个元素，要求时间复杂度O(n)
思路：需要两个指针p1,p2，p1先往前走，p2在p1走了k步之后跟随，这样当p1到了尾部时，p2就到了倒数第k的位置
*/
#include <stdio.h>
#include <iostream>
using namespace std;
// 链表节点类
// 包含_value和_next两个成员
class LinkNode
{
public:
// 构造函数带val和next两个参数，使得可以快速初始化节点
LinkNode(int val, LinkNode* next = NULL) :_value(val), _next(next)
{}
int _value;
LinkNode* _next;
};
// 简单的链表类，为了更清晰的看到这个题目的主题
// 这个链表类操作简单到只有增加数据
class Link
{
public:
LinkNode* _head; // 链表头
Link() : _head(NULL) // 构造函数将链表头初始化成NULL
{}
void add_head(int val) // 在链表头上增加一个节点
{
_head = new LinkNode(val, _head);
}
void print() // 打印链表，看到链表全貌
{
LinkNode* node = _head;
while (node)
{
cout << node->_value << endl;
node = node->_next;
}
cout << "--------------------------" << endl;
}
void find_reverse(int k) // 查找倒数第k个元素
{
// 两个指针，一个先走，一个后面跟随
LinkNode* p1 = _head;
LinkNode* p2 = _head;
printf("find_reverse with k=%d\n", k);
// p1先走
while (p1)
{
--k; // 当p1移动时，对k进行减一
if (k < 0) // 如果k被减到负数，那么p2就要跟随了
{
p2 = p2->_next;
}
p1 = p1->_next;
}
if (k <= 0) // 最后k如果是0或者负数，那么说明k < n，找到数据了，
cout << "find_reverse value=" << p2->_value << endl;
else // 否则k大于n是找不到的，在只有5个节点的链表里，找倒数第10个数是不可能的
cout << "k > n ?" << endl;
}
};
int main()
{
Link l;
// 构造单链表
for (int i = 0; i < 10; i++)
{
l.add_head(i);
}
// 看看单链表如何
l.print();
// 去查找倒数第五个
l.find_reverse(5);
system("pause");
}
代码下载及其运行
代码下载地址：http://download.csdn.net/detail/yincheng01/6704519
解压密码：c.itcast.cn
下载代码并解压后，用VC2013打开interview.sln，并设置对应的启动项目后，点击运行即可，具体步骤如下：
1）设置启动项目：右键点击解决方案，在弹出菜单中选择“设置启动项目”
2）在下拉框中选择相应项目，项目名和博客编号一致
3）点击“本地Windows调试器”运行
程序运行结果