有没有更有效的方法来查找单链表的中间部分？（任何语言）

Question

让我们设置上下文/限制：

1. 链表由节点对象组成

下面是我建议的解决方案的一些代码。

Node cursor = head;
Node middle = head;

while (cursor != null) {
    cursor = cursor.next;
    if (cursor != null) {
        cursor = cursor.next;
        middle = middle.next;
    }
}
return middle;

在不改变链表结构（不切换到双链表或存储长度变量）的情况下，有没有更有效的方法来查找单链表的中间元素？

注意：当此方法找到偶数个节点的中间时，它总是找到左中间。这是理想的，因为它允许您访问两者，但是如果一个更有效的方法总是能找到正确的中间，那也没关系。

Answer 1

不，考虑到你所掌握的信息，没有比这更有效的方法了。

考虑从一个节点到下一个节点的转换。您必须执行N转换来计算列表长度。然后必须执行N/2转换以找到中间位置。

无论您是根据查找到的长度先进行全扫描，然后进行半扫描，还是并行运行光标（速度为两倍）和中间（速度为正常）指针，都与此无关，转换的总数保持不变。

使其更快的唯一方法是向您已经忽略的数据结构引入额外的信息，但是，为了完整起见，我将在这里包含它。例如：

>

使其成为具有head和尾部指针的双链表，因此您可以通过从两端向中间挤压在N转换中找到它。这将指针的存储需求增加了一倍，但是可能不合适。

有一个跳过列表，每个节点都指向它的“子”和“孙子”。这将加速cursor转换，导致总共只有大约N（即每个cursor和中间的N/2）。像前一点一样，每个节点需要一个额外的指针。

单独维护列表的长度，以便您可以在N/2转换中找到中间。

与上一点相同，但在某些情况下缓存中间节点以提高速度。

最后一点需要额外检查。像许多优化一样，您可以用空间换取时间，缓存显示了一种方法。

首先，保持列表的长度和指向中间节点的指针。长度最初为零，中间指针最初设置为null。

如果在长度为零时要求使用中间节点，只需返回null。这是有道理的，因为列表是空的。

否则，如果您被要求输入中间节点，而指针为null，那一定是因为您还没有缓存该值。

在这种情况下，使用长度（N/2transitions）计算该指针，然后在返回该指针之前存储该指针以备将来使用。

顺便说一句，当添加到列表末尾时，这里有一个特殊的情况，一些足够常见的情况需要特殊的代码。

当长度从偶数增加到奇数时，只需将middle设置为middle即可-

这将保存重新计算并起作用，因为您（a）有下一个指针，并且（b）您可以计算出中间“索引”（基于一个索引，并根据原始问题选择一对索引的左边）在给定长度时的变化：

Length   Middle(one-based)
------   -----------------
     0      none
     1         1
     2         1
     3         2
     4         2
     5         3
     :         :

这种缓存意味着，如果列表不发生变化（或者只在末尾发生变化），下次您需要中间元素时，它几乎是即时的。

如果从列表中删除节点（或插入endpoint以外的其他位置），请将中间指针设置回null。然后在下次需要时重新计算（并重新缓存）。

因此，对于最小的额外存储需求，您可以获得相当大的速度，特别是在需要中间元素的情况下，而不是在更改列表的情况下。