算法与数据结构面试题

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

更新: 2020-07-28 19:43:43
原文: <https://www.yuque.com/fcant/notes/uz9zxq&gt;