你将如何遍历O(n ^ 0.5)中的链表？

Question

这是Apple的采访问题.我发现没有令人信服的论据支持或反对它.

Answer 1

比 O(n) 更高效的遍历是不可能的，因为“遍历”需要依次访问每个节点。

不过，通过维护第二个保留中间节点链接的链表，可以使随机访问速度比 O(n) 更快；然而，由于第二个列表的维护复杂性增加，插入、删除和附加成本将会增加。