这是一道面试的算法题。
给一个单向链表，节点的值为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
网友评论