快慢指针解法
链表中倒数第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个结点