11

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

5 回答 5

8

如果我们将代码修改为：

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

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

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

于 2013-06-25T23:44:32.607 回答
4

正如@Oleg Mikheev 所建议的，为什么我们不能使用弗洛伊德的寻环算法来找到中间元素，如下：

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;
    }
于 2016-01-16T12:51:48.923 回答
1

第一个答案有多个优点：

  1. 由于这两种方法具有相同的复杂度 O(N)，因此任何关于效率的分析都需要谨慎，可能涉及到具体的实现和成本模型。然而，对于最幼稚的实现，第一种方法可以节省一些循环变量增量。

  2. 它为您节省了一个变量的空间——两个指针与长度、计数器和一个指针。另外，如果它是一个巨大的列表，并且长度溢出怎么办？

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

于 2013-06-25T23:47:55.230 回答
0 
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->

5

于 2014-07-19T18:54:45.093 回答
0

这是经典的求职面试问题。

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

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

于 2015-10-09T07:06:47.363 回答