java - 通过 1 遍查找链表的中间元素，这是创意 "useless answer"吗？

Question

假设您想以尽可能高效的方式找到链表的中间节点。给出的最典型的“最佳”答案是保持2个指针，一个中间，一个当前。并在遇到的元素数可被 2 整除时增加中间指针。因此，我们可以在 1 遍中找到中间点。高效，对吧？比蛮力更好，后者涉及 1 次传递到最后，然后再传递 1 次直到我们达到 size/2。

但是......没那么快，为什么第一种方法比“蛮力”方式更快？在第一种方法中，我们将中间指针递增大约 size/2 倍。但是以蛮力的方式，在我们的第二遍中，我们遍历列表直到我们到达 size/2th 节点。那么这两种方法不是一样的吗？为什么第一个比第二个好？

//finding middle element of LinkedList in single pass
          LinkedList.Node current = head;
          int length = 0;
          LinkedList.Node middle = head;

          while(current.next() != null){
              length++;
              if(length%2 ==0){
                  middle = middle.next();
              }
              current = current.next();
          }

          if(length%2 == 1){
              middle = middle.next();
          }

Answer 1

如果我们修改代码为:

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

现在赋值变少了，因为 length 不必递增，我相信这会产生相同的结果。

归根结底，这两种解决方案都是 O(N)，因此这是一个微观优化。