我们有一个大小为 L 的链表，我们想检索最后一个元素的第 n 个。
解决方案 1：幼稚的解决方案
- 从开始到结束进行第一次传递以计算L
- 从起点到预期位置进行第二次传递
解决方案 2：使用 2 个指针 p1、p2
- P1 从头开始迭代，P2 不移动。
- 当 P1 和 P2 之间有
n元素时，P2 也开始迭代 - 当 P1 到达列表末尾时，P2 处于预期位置
两种解决方案似乎具有相同的时间复杂度（即，对列表元素进行2L - n迭代）哪一个更好？
算法都是两次通过的。对于相当小的 n，第二个通道可能具有更好的性能，因为第二个过程访问第一个传递已缓存的内存。 （传递是交错的。
一次性解决方案会将指针存储在循环缓冲区或队列中，并在到达列表末尾后返回队列的"头"。
使用 3 个指针 p、q、r 和一个计数器怎么样？
使用 p 更新计数器循环访问列表。每 n 个节点将 r 分配给 q，将 q 分配给 p
当你点击列表的末尾时，你可以弄清楚有多远。r 来自列表的末尾。
您可以在不超过 O（L + n） 内得到答案
如果n << L，解决方案 2 通常更快，因为缓存，即包含 p1 和 p2 的内存块被复制到 CPU 缓存一次，指针在需要再次访问 RAM 之前移动一堆迭代。
简单地将链表的长度存储在 O（1） 内存中不是便宜得多吗？你必须做"第一次传递"的唯一原因是因为你不知道链表的长度。如果存储长度，则可以迭代 （|L|-n） 元素，每次都可以轻松检索元素。对于与 L 相比更高的 n 值，这种方式将为您节省大量时间。例如，如果 n 等于 |L|，您可以简单地返回列表的头部
，根本不进行迭代。此方法使用的内存比第一个算法略多，因为它将长度存储在内存中，但第二个算法使用两个指针，而此方法仅使用 1 个指针。如果你有第二个指针的内存，你可能有内存来存储链表的长度。
授予 O（|L|-n）等价于纯理论中的O（n），但有"快速"线性算法，然后有"慢"线性算法。这种问题的两遍算法很慢。
正如@HotLicks在评论中指出的那样，"人们需要明白，在许多情况下，'大O'复杂性与实际性能只有松散的关系，因为它忽略了加性因素和恒定的乘数。在这种情况下，IMO 只是选择最懒惰的方法，不要想太多。