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

假设您想以尽可能有效的方式找到链表的中间节点。给出的最典型的“最佳”答案是保持 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();
          }

最佳答案

如果我们修改代码为:

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

现在分配更少了，因为 length 不必递增，我相信这会给出相同的结果。

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

关于java - 通过 1 次查找链表的中间元素，这是一个创意 "useless answer"吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17309300/