java - 在链接列表中查找最小值

Question

我正在尝试在顶点链接列表中找到最小值。这是我写的，但它是错误的。我没有收到错误，但我的程序无法运行，我认为这是错误的来源。我究竟做错了什么？

      Iterator itr = vertices.iterator();
      Vertex smallest= getVertex(s);
      Vertex temp;
      while (itr.hasNext()){
          smallest=(Vertex)itr.next();
           if(itr.hasNext() && vertices.size()> 1 ){//there are at least 2 vertices left
                temp = (Vertex)itr.next();
                if (temp.distance< smallest.distance){
                    smallest = temp;
                }
          }
     }

Answer 1

问题是您在每次迭代中都从迭代器中消耗了两个元素(通过 itr.next())，所以这意味着您只比较了一些元素:

1----2----3-----4-----5-----6
\----/    \-----/     \-----/

你比较 1 和 2； 3 和 4； 5 和 6；但不是 2 和 3； 4 和 5。

解决这个问题最简单的方法是保留之前的顶点:

Vertex prev = itr.next();
while (itr.hasNext()) {
  Vertex current = itr.next();

  // Compare prev and current

  prev = current;
}

另请注意，如果您使用类型参数声明迭代器，则可以避免强制转换 (Vertex):

Iterator<Vertex> itr = vertices.iterator();