【算法】-求单向链表的倒数第k个值

这是一道面试的算法题。

给一个单向链表，节点的值为int型，求倒数第k个节点的值。

一开始，想到的思路是先求出链表的长度len，然后再遍历一次求第len-k个的值，这样共需要遍历两次链表，时间较长。

后来，想到可以用堆栈，把链表的值一个个push入栈，全部入栈后，再pop出栈k-1个节点，则当前栈顶就是所求的解。但是这个方法需要额外的空间，也不太好。

其实，有一种只需要遍历一次，不需要额外空间的算法。给定两个指针，i和j。过程如下。

初试状态时，i和j都在表头位置。首先，i先从表头开始走k-1步；然后，j也开始从表头走，i和j每次都走一步，直到i先走到表尾，此时，j所指向的节点的值就是要求的解。

假设k==4

初始状态 i先走k-1步 结束状态

代码如下

运行结果为 倒数第k个值为:2