快慢指针解法
链表中倒数第k个结点
http://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a
假设链表长度为n，则可以将链表分成3部分：
- 起点 [1,1]
- 第二个结点到第n-k个结点 [2, n-k]
- 倒数第k个结点到第n个结点 [n-k+1, n]
划分如图：
所以结点从起点开始走n-k-1+1 = n-k步就到达倒数第k个结点。
也就是要计算出n-k的长度。
那么根据输入的参数k，设置快慢指针可以达到目的
设置快慢指针，让两者指向第一个结点
然后，先让快指针从起点走k步，此时访问的表长为k+1个结点，所以剩下的结点加上链表尾后的空位置共有n-(k+1)+1 = n-k个结点；
然后，让快慢指针同步向前走，当快指针到达空位置，两个指针都走了n-k步，即慢指针到达倒数第k个结点
腾讯公司福利 857人发布
韶音科技开奖52人在聊
