常见算法之19---输出链表的倒数第k个节点

题目:输入一个单向链表,输出该链表中倒数第 k 个结点。


方案一:先遍历一遍,获取到链表的长度n,然后从头再走n-k步。
分析:相当于遍历两遍,第一遍是为了获得链表的长度,而第二遍是找到倒数第k个节点。

方案二:
一个盲人怎么才能知道他到墙的距离是d?
他可以拿一个长度为d的杆子,当杆子碰到墙了,此时他到墙的距离就是d了。

基于上面的思想:
1.指定一个新的指针p,走k步。如果k步之内就到了null,显然无倒数第k这说法,返回错误即可。
2.新指针p到位后,在初始节点再设定一个新的指针root,然后两个指针一起走。当p为null时,输出root所指的节点即可。

原文地址:https://www.cnblogs.com/xiaoChongUp/p/3394830.html