【算法】-求单向链表的倒数第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

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容