查找单链表的第k个最后元素：答案说明

Question

当您需要查找单列列表的kth最后一个元素时，通常的简单方法是执行两个过程。第一个查找列表的长度，第二个迭代到（length-k）th元素。

而优化版本利用了两个指针：

• p1引用列表的头部
• p2是k在p1
之前的第2个元素

这允许我们在p2到达列表末尾时返回p1的元素。我不明白为什么第二种方法比第一种更快，因为在这两种情况下，我们都有一个指针遍历整个列表，另一个指针一直迭代到（length-k）th元素。

这是因为缓存优化吗？

谢谢

Answer 1

考虑非均匀的内存访问时间和长度为n的单链表：
-在计数迭代方法中，对同一节点的访问将是n次访问间隔
-在滞后指针方法中，对同一节点的访问将是k次访问间隔
对于LRU缓存（/每个LRU缓存级别），前者比后者更有可能导致容量缺失。

Answer 2

如果您将p2完全k元素保留在p1后面，那么它实际上没有多大帮助，因为您必须一起执行相同数量的遍历。

不过，您可以通过使用更多指针来优化过程。

当你浏览列表时，假设你记住了每个（k/m）位置的指针，对于一些m，你只需要记住这些指针中最后的m1。然后，当您到达列表的末尾时，不要从头开始重复，而是从您记得的最早的指针开始。它将在末端后面的k和k（k/m）元素之间，因此您只需将其向前移动最多k/m个位置。