我们知道，在给定头指针的情况下，对单链表的查找是O（n）。假设我始终将指针保持在链接列表的一半。我会改进查找时间吗？
是的，如果您有某种方法来确定是从列表的开头还是中间开始（通常但不一定是要排序的列表），它可以将复杂性降低2的常数。然而，这是一个不变的因素，所以就大O复杂性而言，这是无关紧要的。
为了与大O复杂性相关，您需要的不仅仅是一个恒定的因素变化。例如，如果你有一个指针来平分每一半，再平分每一半等等，你最终会得到对数复杂度，而不是线性复杂度——你会把你的"链表"转换成一个（众所周知的）线程树。
想法不错，但这仍然没有改善搜索操作。无论在列表的不同部分有多少指针，都必须分析列表中的每个元素。然而，您可以使用两个线程来搜索列表的每一半，从而使操作速度在理论上提高一倍。
仅当链接列表的数据已排序时。否则，正如在另一个答复中已经说过的那样。
它会，但渐近地它仍然是一样的。然而，有一种数据结构使用了这种思想，它被称为跳过列表。跳过列表是一个链表，其中一些节点有更多的指针，这些指针在某种意义上指向列表其余部分的中间。这张图片很好地说明了这个想法。此结构通常具有对数插入查找和删除功能。