algorithm - 查找单链表的倒数第 k 个元素 : answer explanation

Question

当您需要查找单向链接列表的第 k 个最后一个元素时，通常的朴素方法是执行两次遍历。第一个找到列表的长度，第二个迭代直到 (length-k)th 元素。

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

• p1 指向链表的头部
• p2 是 p1
之前的 k 个元素

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

是缓存优化的原因吗？

谢谢。

Answer 1

如果您将 p2 恰好保留在 p1 之后的 k 个元素，那么它并没有多大帮助，因为您必须执行相同的操作一起遍历的次数。

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

当您浏览列表时，假设您记得指针在每个 (k/m)th 位置，有一些 m。您只需要记住这些指针的最后一个 m+1。然后，当你到达列表的末尾时，不要从头开始迭代，而是从你记得的最早的指针开始。它会在 k 和 k + (k/m) 元素之间，所以你最多只需要将它向前移动 k/m 个职位。