如何找出单链表中的倒数第k个元素？

思路一：初看题目，最容易想到的方法就是遍历。首先遍历一遍单链表，得出整个链表的长度n（元素个数从1到n），然后找到倒数第k个元素的位置n-k+1，接着从头遍历到第n-k+1元素，就是倒数第k个元素。但是该方法需要对链表进行两次遍历，遍历的元素个数为n+n-k+1=2n+1-k个。
思路二：有了思路一的提示，是不是可以想到用两个指针，让它们之间的距离保持为k-1，同时对链表进行遍历，当第一个指针到达链表的最后一个元素（即倒数第一个元素时），第二个指针刚好停留在倒数第k个元素上。此方法看似对链表进行了一次遍历，其实是用两个指针对链表进行了同时遍历，对链表本身而言，它被遍历的元素个数仍是n+n-k+1=2n+1-k个。
思路三：思路一和思路二是两种不同思路，但就本质而言，都是两次对链表进行2次遍历，一次遍历n个元素，另一次遍历n-k+1个，总共遍历2n+1-k个元素。此时，想想能否再减少遍历的元素个数而找到倒数第k个元素呢？注意到思路二，是用两个指针，保持k-1个元素的距离同时进行遍历的，可否按着每次k个元素这样的遍历下去呢。这样遍历的结果就是，每次遍历k个元素，遍历m次（m=n/k），最后一次遍历的个数为i个（i=n%k），只需记录最后一次遍历k个元素的起始位置，然后再遍历i个元素，此时的位置即为倒数第k个元素。此时，对链表遍历的元素个数为n+i（i为n除以k的余数）。