相关疑难解决方法(0)

假设您希望尽可能高效地找到链表的中间节点.给出的最典型的"最佳"答案是保持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();
          }

如何在没有遍历的情况下在单链表中找到中间节点？

它有可能在第一位吗？

在一次遍历中我使用传统方法使用2个指针,一个跳跃的2个位置,另一个跳跃的一个位置..是否有任何其他方法在一次遍历中找到中间节点