单链表查寻倒数第i个结点，linux纯C实现

单链表查找倒数第i个结点，linux纯C实现

本例中使用的单链表库是自己编写的，在前面博文中有提到过：

http://blog.csdn.net/lvjing2/article/details/14045011

这次关于单链表的算法，就是引用这个库进行实现的，所以如果需要测试本算法，就需要拷贝下前文中的代码了。好了，废话不多说了。

输入一个单链表，输出该链表倒数第i个结点。链表的倒数第0个结点为该链表的尾指针。

1. 最容易想到的是，先走到链表的尾结点，然后回溯到倒数第i个结点。但是算法要求中的是单向链表，故指针是无法从后往前的。

2. 既然无法从后往前，那可以遍历整个链表求出整个链表的长度n，然后就可知道，倒数第i个结点就是第n-i-1个结点。然后再从头结点走到地n-i-1个结点，从而找到该结点。

    但这样需要遍历链表两次，第一次得到链表结点个数n，第二次得到从头结点开始的第n-i-1个结点，即倒数第i个结点。如果结点不多，这是一种可行的方法。但当结点很多时，有可能不 能一次性把整个链表从硬盘读入内存，那么两次遍历结点就意味着需要两次从硬盘读入到物理内存，而这样的时间消耗是非常大的。所以我们还将寻找更好的方法来更好地解决这个问题。

3. 下面介绍的是只通过一次遍历找到倒数第i个结点的方法。

a. 定义两个指针：p1, p2.初始化两个指针都指向头结点。

b. p1指针开始遍历,p2保持不动。

c. 当p1遍历到第i个结点后，p2开始遍历。(这样p1和p2指针的距离永远保持i个结点的距离)

d. 当p1遍历到链表尾指针时，返回p2.

position FindFromLast(list L, int indexRev){position p1 = L, p2 = L;int i1 = 0;while(p1->next){i1++;p1 = p1->next;if(i1 > indexRev){p2 = p2->next;}}return p2;}