剑指offer 原题
热度 【美团】
输入一个链表，输出该链表中倒数第k个节点，为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第一个节点，
例如，一个链表有6个节点，从头节点开始，他们的值依次是1、2、3、4、5、6.这 个链表的倒数第3个节点的值是值为4的节点。
思路
方法一 hash表获取
我们将遍历链表以后将数值存入hash表。《位置，节点》、然后计数出倒数的是第几个节点，如n是链表的长度，要求取到倒数第k个数，那么倒过来计算正数的值就是
n-k+1。 直接去hash.get（n-k+1）.得到节点值。
时间复杂度为O【n】.
空间复杂度为O【n】
方法二 快慢指针
如果要求时间复杂度是O(n)，空间复杂度是o(1) 。那么hash就 不符合要求了。这时就得另辟蹊径。
这个时候我们，想到了使用快慢指针的方式。快慢指针首先都同时指向链表头head。若我们要取倒数第2个节点的值。，设k=2 .那么快指针先走k-1步。即快指针先移动（2-1）=1步。
然后此时慢指针始终笔快指针慢1步。快慢指针同时移动，直到快指针到达链表尾部时。慢指针恰好指向链表后的倒数第2个节点。我们刚好能取到倒数第2个节点的值
这方法还真是巧妙至极，简直是妙蛙种子走进了家了，妙妙妙啊 ~
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
