algorithm - 查找单链表的第 k 个最后一个元素：答案解释

Question

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

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

• p1引用列表的头部
• p2k领先于元素p1

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

是因为缓存优化吗？

谢谢。

标签： algorithmlinked-listsingly-linked-list

Answer 1

如果您将p2元素保留k在后面p1，那么它并没有太大帮助，因为您必须一起进行相同数量的遍历。

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

当您浏览列表时，假设您记住了每个(k/m)th位置的指针，对于某些m。您只需要记住这些指针的最后m+1个。然后，当你到达列表的末尾时，不要从头开始迭代，而是从你记得的最旧的指针开始。它将在末端后面的k和k + (k/m)个元素之间，因此您只需将其向前移动最多k/m 个位置。