在最近的一次采访中，我被问到：
从第一个位置开始查找未知长度的排序列表的中间元素。
我回答这个问题：
有2个位置计数器：
计数器1 计数器2
将counter1递增1，将counter2递增2.当计数器2到达列表的末尾时，计数器1将位于中间。我觉得这样做效率不高，因为我正在重新审视我已经看过的节点。无论哪种方式，是否有更高效的算法？
在最近的一次采访中，我被问到：
从第一个位置开始查找未知长度的排序列表的中间元素。
我回答这个问题：
有2个位置计数器：
计数器1 计数器2
将counter1递增1，将counter2递增2.当计数器2到达列表的末尾时，计数器1将位于中间。我觉得这样做效率不高，因为我正在重新审视我已经看过的节点。无论哪种方式，是否有更高效的算法？
假设有一个链表，你可以在任意接近N个项目时进行。
做5/4 N：
当您点击列表的末尾时，前一个锚点位于中点之前，但至少已经有一半。所以N为完整迭代+最多1/4 N为锚= 5/4 N.
更频繁地丢弃锚点，例如在第1.5项的每个上限功率下，根据需要使你接近N（以跟踪更多锚点为代价;但对于任何给定的X作为功率步长，渐近记忆是恒定的） 。
我假设你正在讨论一个链表。确实，您的解决方案非常出色。另一种方法是简单地遍历列出元素数量的列表，然后从头开始，遍历计算量的一半。两种方法最终都会遍历 3n/2 节点，所以没有太大区别。
根据架构的不同，任何一种方法都可能存在轻微的缓存优势;第一种方法可能具有缓存节点的优势，如果缓存足够大，则在两个指针相距很远之前，这可能意味着更快的检索。或者，如果我们一次遍历列表，缓存可能会获得更好的块，而不是保持两个指针活着。
假设你可以检测到你已超出列表的末尾并在列表中有效地寻找任意位置，你可以保持列表的假定长度加倍（猜测长度为1，然后是2，然后是4，...... ）直到你超过列表的末尾，然后在最后尝试的值小于列表长度和超出列表末尾的第一个值之间使用二进制搜索来查找列表的实际结束。
然后，寻找位置END_OF_LIST / 2。
这样，您就不必访问每个节点。
从技术上讲，如果您使用O（N）内存（假设您正在使用链接列表），则可以在一次遍历中执行此操作。
编辑：我确实喜欢你的答案！
假设常规的内存中链表允许读取下一个元素，给出当前多次引用（免责声明，未经测试，但该想法应该有效）：
// assume non-empty list
slow = fast = first;
count = 0;
while (fast)
{
fast = fast.next;
if (!fast)
break;
count++;
fast = fast.next;
if (fast)
count++;
slow = slow.next;
}
if (count % 2)
return slow.data;
else
return (slow.data + slow.next.data)/2.0;
更难的情况是“列表”不是内存中的链接列表，而是一个可以按排序顺序读取的流以及只读取一次的每个元素的内容，我没有一个很好的解决方案。