让我们设置上下文/限制:
- 由Node对象组成的链表。
- 节点只有对下一个节点的引用。
- 对列表的引用只是对头节点对象的引用。
- 除了构建之外，没有对链表进行任何预处理或索引(没有其他引用内部节点或收集的统计数据，即长度)。
- 列表中的最后一个节点的下一个节点的引用为空。
下面是我提出的解决方案的一些代码。
Node cursor = head;
Node middle = head;
while (cursor != null) {
cursor = cursor.next;
if (cursor != null) {
cursor = cursor.next;
middle = middle.next;
}
}
return middle;
在不改变链表结构(不切换到双链表或存储长度变量)的情况下，是否有更有效的方法来找到单链表的中间元素?
注意:当此方法找到偶数个节点的中间时，它总是找到左中间。这是理想的，因为它让您可以同时访问两者，但如果更有效的方法总是能够找到正确的中间，那也很好。
不，考虑到你现有的信息，没有比这更有效的方法了。
想想从一个节点到下一个节点的转换。您必须执行N转换以计算列表长度。然后让执行N/2转换以找到中间。
无论您是基于发现的长度进行完全扫描，然后进行半扫描，还是并行运行cursor(以两倍速度)和middle(以正常速度)指针，这里都不相关，转换的总数保持不变。
使其更快的唯一方法是将额外的信息引入到您已经忽略的数据结构中，但是为了完整性，我将在这里包括它。例如:
-
使其具有
head和tail指针的双链表，因此您可以通过从两端到中间"挤压"来找到N转换。这将使指针的存储需求翻倍，因此可能不合适。 -
有一个跳跃列表，每个节点都指向它的"子节点"one_answers"孙子节点"。这将加速
cursor的转换，导致总共只有大约N(即cursor和middle各为N/2)。与前一点一样，每个节点需要一个额外的指针。 -
单独维护列表的长度，以便您可以在
N/2转换中找到中间位置。 -
与前一点相同，但在某些情况下缓存中间节点以增加速度。
最后一点需要一些额外的检查。像许多优化一样，您可以用空间换取时间，缓存显示了一种方法。
首先，保持列表的长度和指向中间节点的指针。长度初始值为0，中间指针初始值为null。
当长度为0时，如果您被要求查找中间节点，只需返回null。这是有意义的，因为列表是空的。
否则，如果你被要求查找中间节点，而指针是null，那一定是因为你还没有缓存这个值。
在这种情况下，使用长度(N/2转换)计算它，然后存储指针以供以后返回。
当长度从偶数变为奇数时，将middle设置为middle->next，而不是将其设置为null。
这将节省重新计算和工作，因为你(a)有next指针和(b)你可以计算出中间的"索引"(基于一个并根据你原来的问题选择一对的左边)如何改变给定的长度:
Length Middle(one-based)
------ -----------------
0 none
1 1
2 1
3 2
4 2
5 3
: :
这个缓存意味着，如果列表没有改变(或者只在末尾改变)，下一次你需要中间元素的时候，它将几乎是瞬间的。
如果要从列表中删除一个节点(或在末尾以外的地方插入节点)，请将中间指针设置为空。然后在下次需要时重新计算(并重新缓存)。
因此，对于最小的额外存储需求，您可以获得相当多的速度，特别是在需要中间元素比列表更改更频繁的情况下。