这是苹果公司的一个采访问题。我还没有找到任何令人信服的论据来支持或反对它。
遍历不可能比O（n）更高效，因为"遍历"需要依次访问每个节点。
不过，通过维护保留到中间节点的链接的第二个链表，可以使随机访问比O（n）更快；但是，由于第二个列表维护的复杂性增加，插入、删除和追加成本将增加。
不可能
这是假设您的意思是查看n个节点的链接列表中的每个节点。这可能是一个技巧性的问题，看看你是否能弄清楚这是不可能的。
当我第一次遇到这个问题时，我和这里的大多数人一样认为：这是不可能的，一个技巧问题，某种心理测试。我错了。
真正的答案是，至少在理论上，使用量子计算机可以比O（N）更快地遍历列表。
查看维基百科上关于Grover算法的文章。
它们规定了O（n^0.5）的摊余运行时间和O（logn）的空间。还应该注意的是，它不是确定性的。这意味着算法很有可能返回正确的结果，但这并不能保证。
我想这已经足够通过这个问题了，但其余的都超出了我的想象。
祝你好运。
也许每个节点都有到下一个元素、上一个元素和中心元素的连接（其中中心是当前元素和列表末尾之间的中点）。
想法？