java用1次遍历查找链表的中间元素，这是一个创造性的“无用答案”吗？

Question

假设您希望以尽可能高效的方式找到链接列表的中间节点。给出的最典型的“最佳”答案是维护两个指针、一个中间指针和当前指针。当遇到的元素的#可被2整除时，增加中间指针。因此，我们可以在一个过程中找到中间。效率高，对吧？比蛮力好，蛮力需要一次传球到终点，然后再传球一次，直到我们达到大小/2

但是。。。不是那么快，为什么第一种方法比“蛮力”方法快？在第一种方法中，我们将中间指针的大小增加大约/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

第一个答案有多个优点：

1. 由于这两种方法具有相同的复杂性O（N），任何关于效率的分析都需要小心，可能涉及具体的实现和成本模型。然而，对于最简单的实现，第一种方法可以节省一些循环变量增量

2. 它节省了一个变量的空间——两个指针vs.长度、计数器和一个指针。此外，如果这是一个巨大的列表，并且长度溢出了呢

但是，如果你考虑一些特定的模型，那么第二种方法可能会更好。如果元素在内存中都是相邻的，并且列表足够大，则缓存只能容纳一个连续内存位置，第一种方法可能会产生一些内存访问成本。归根结底，这两种方法基本上是等效的。当然，第一种方法中使用的技巧更浮华，思维过程可能在其他情况下有用

Answer 2

public void middle(){
    node slow=start.next;
    node fast=start.next;
    while(fast.next!=null)
    {
        slow=slow.next;
        fast=fast.next.next;
    }

    System.out.println(slow.data);
}

10->；9->；8->；7->；6->；5->；4->；3->；2->；1->

五,

Answer 3

如果我们将代码修改为：

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

现在作业少了，因为length不必递增，我相信这会给出相同的结果

最终，两种解决方案都是O（N），因此这是一种微观优化

Answer 4

正如Oleg Mikheev所建议的，为什么我们不能用Floyd's cycle-finding algorithm来找到中间元素，如下所示：

private int findMiddleElement() {
        if (head == null)
            return -1; // return -1 for empty linked list
        Node temp = head;
        Node oneHop, twoHop;
        oneHop = twoHop = temp;
        while (twoHop != null && twoHop.next != null) {
            oneHop = oneHop.next;
            twoHop = twoHop.next.next;
        }
        return oneHop.data;
    }

Answer 5

这是典型的面试问题

他们不希望你使用算法O（n），因为它们都有O（n）的复杂性。普通人会说，如果我不遍历一次，就无法知道中间位置在哪里（所以遍历一次以找到长度，遍历第二次以找到中间位置对于采访你的人来说是两个通行证）。他们希望你们跳出框框思考，找出你们提到的方法，其中包括两个指针

所以复杂性是一样的，但思维方式是不同的，面试的人你想看到这一点