有没有更有效的方法来找到单链表的中间？ （任何语言）
Is there a more efficient way to find the middle of a singly-linked list? (Any language)
让我们设置 context/limitations:
- 一个链表由 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 transitions by "squeezing" 中找到它从两端到中间。这使指针的存储要求加倍，但可能不合适。
有一个跳跃列表，每个节点都指向它的 "child" 和它的 "grandchild"。这将加速 cursor 转换，导致总共只有大约 N（即 cursor 和 middle 中的每一个的 N/2）。与前一点一样，每个节点都需要一个额外的指针。
单独维护列表的长度，以便您可以在 N/2 转换中找到中间部分。
与上一点相同，但在某些情况下缓存中间节点以提高速度。
最后一点需要额外检查。与许多优化一样，您可以用 space 换取时间，缓存显示了一种方法。
首先，维护链表的长度和一个指向中间节点的指针。长度初始为零，中间指针初始设置为 null.
如果在长度为零时要求您提供中间节点，只需 return null。这是有道理的，因为列表是空的。
否则，如果你要求中间节点，指针是null，那肯定是因为你还没有缓存值
在这种情况下，使用长度（N/2 转换）计算它，然后 存储 该指针以备后用，在 return 之前 return。
顺便说一句，添加到列表的 end 时有一种特殊情况，这种情况很常见，需要特殊代码。
当长度从偶数变为奇数时添加到末尾时，只需将 middle 设置为 middle->next 而不是将其设置回 null。
这将节省重新计算并起作用，因为您 (a) 有 next 指针，并且 (b) 您可以算出中间 "index"（基于一并选择根据你原来的问题一对）改变给定的长度：
Length Middle(one-based)
------ -----------------
0 none
1 1
2 1
3 2
4 2
5 3
: :
这种缓存意味着，如果列表不变（或仅在末尾发生变化），下次您需要中间元素时，它几乎是瞬时的。
如果您曾经从列表中删除一个节点（或在末尾以外的地方插入），请将中间指针设置回空。下次需要时将重新计算（并重新缓存）它。
因此，对于最小的额外存储要求，您可以获得相当多的速度，尤其是在需要中间元素的频率高于列表更改频率的情况下。
让我们设置 context/limitations:
- 一个链表由 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指针的双向链表，所以你可以在Ntransitions by "squeezing" 中找到它从两端到中间。这使指针的存储要求加倍，但可能不合适。有一个跳跃列表，每个节点都指向它的 "child" 和它的 "grandchild"。这将加速
cursor转换，导致总共只有大约N（即cursor和middle中的每一个的N/2）。与前一点一样，每个节点都需要一个额外的指针。单独维护列表的长度，以便您可以在
N/2转换中找到中间部分。与上一点相同，但在某些情况下缓存中间节点以提高速度。
最后一点需要额外检查。与许多优化一样，您可以用 space 换取时间，缓存显示了一种方法。
首先，维护链表的长度和一个指向中间节点的指针。长度初始为零，中间指针初始设置为 null.
如果在长度为零时要求您提供中间节点，只需 return null。这是有道理的，因为列表是空的。
否则，如果你要求中间节点，指针是null，那肯定是因为你还没有缓存值
在这种情况下，使用长度（N/2 转换）计算它，然后 存储 该指针以备后用，在 return 之前 return。
顺便说一句，添加到列表的 end 时有一种特殊情况，这种情况很常见，需要特殊代码。
当长度从偶数变为奇数时添加到末尾时，只需将 middle 设置为 middle->next 而不是将其设置回 null。
这将节省重新计算并起作用，因为您 (a) 有 next 指针，并且 (b) 您可以算出中间 "index"（基于一并选择根据你原来的问题一对）改变给定的长度：
Length Middle(one-based)
------ -----------------
0 none
1 1
2 1
3 2
4 2
5 3
: :
这种缓存意味着，如果列表不变（或仅在末尾发生变化），下次您需要中间元素时，它几乎是瞬时的。
如果您曾经从列表中删除一个节点（或在末尾以外的地方插入），请将中间指针设置回空。下次需要时将重新计算（并重新缓存）它。
因此，对于最小的额外存储要求，您可以获得相当多的速度，尤其是在需要中间元素的频率高于列表更改频率的情况下。