我们有一个大小为 L 的链表，我们想要检索倒数第 n 个元素。
解决方案一:天真的解决方案
- 从头到尾进行第一次遍历计算L
- 从起点到预期位置进行第二次传球
方案二:使用2个指针p1,p2
- p1从头开始迭代，p2不动。
- 当p1和p2之间有
n个元素时，p2也开始迭代 - 当p1到达链表末尾时，p2在预期位置
这两种解决方案似乎具有相同的时间复杂度(即 2L - n 对列表元素的迭代)
哪个更好？
最佳答案
这两种算法都是两次通过的。对于相当小的 n，第二个可能有更好的性能，因为第二遍访问已经被第一遍缓存的内存。 ( channel 是交错的。)
一次性解决方案会将指针存储在循环缓冲区或队列中，并在到达列表末尾时返回队列的“头”。
关于algorithm - 获取链表中倒数第 n 个元素，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18819023/