在一个有N个元素的单链表中找出倒数第K 个元素

诡异的很.
已经知道有N个元素了? 那倒数跟正数有什么区别? 倒数第K个, 就是正数第 N-K+1个, 那指针从头节点开始移动, 移动 N-K+1 返回的就是所要元素了.
如果不知道有多少个元素的话, 只能建一个队列了, 队列的长度为K, 用指针从头结点开始搜索, 然后一个一个结点开始进队, 队列满了就前面的出去. 到指针指向尾结点的时候, 队列的第一个元素就是倒数第K个了.
具体的算法就自己写吧. 也不复杂.

计算数组中第i大小元素的select算法：
将n个输入元素划分成「n/5」个组,每组5个元素,只可能有一组元素不是5个。用任意一种排序算法，将每组中的元素排好序，并取每组的中位数，共「n/5」个。
递归调用算法select来找出这「n/5」个元素的中位数。如果「n/5」是偶数，就找它的两个中位数中较大的一个。以这个元素x作为划分基础。
每次数组a[p,r]被划分成为两个子数组a[p:x]和a[x+1:r]，使得a[p:x]中元素都不大于a[x+1:r]中元素。接着计算a[p:x]中元素个数，如果小于i则对a[x+1:r]进行下一次操作，如果大于等于i则对a[p:x]进行下一次操作。
算法分析：
因为每次找出的基准x至少比3[(n-5)/10]个元素大，至少比3[(n-5)/10]个元素小，当n≥75时，3[(n-5)/10]≥n/4。所以按此基准划分所得的两个子数组的长度都至少缩短1/4。
于是，按照算法所选的基准进行划分所得到的2个子数组分别至多有3n/4个元素。设对n个元素调用算法select需要T(n)的时间，找中位数x至多用了T(n/5)的时间，无论对哪个子数组调用函数都至多用T(3n/4)。至
得到递归式:
T(n)≤C n<75
T(n）≤C*n+T(n/5)+T(3n/4) n≥75
解得递归式可得T(n)=O(n)。

找本算法书吧，里面一般是有的