如何找出单链表中的倒数第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的余数）。

• 总结：思路一和二的本质虽相同，但是思路二却是一种更高效的实现，思路三属于另一种额外，需要跳出保持k-1个距离的限制。比较下两种遍历中遍历元素的个数，在n固定的情况下，遍历的元素个数取决于k，即k的变动会引起遍历个数的不同，而思路三中，真正决定遍历个数的却是i，即在i相同的情况下，即使k不同，遍历的个数也有可能是相同的。应该值得注意的是，在n>k的情况的，n+i<2n+1-k。

• 本次思路分析中并未考虑链表为空，和n<=k的情况，请在实现时，加入此类条件判断。

转自