用1遍查找链表的中间元素,这是一个创造性的"无用的答案"吗？

Question

假设您希望尽可能高效地找到链表的中间节点.给出的最典型的"最佳"答案是保持2个指针,一个中间和当前.当遇到的元素数被2整除时,增加中间指针.因此,我们可以在1遍中找到中间值.高效,对吗？比蛮力更好,包括1次传递到最后,然后再传1次直到我们达到/ 2.

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

//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),因此它是微优化.