java - 从 Java 链表中删除最小元素

Question

我正在尝试从 Java LinkedList 中删除最小元素。

为了找到最小值，我必须遍历一次LinkedList。我想保存该元素的节点或迭代器以在 O(1) 中将其删除。

正常

list.remove(Object o)

需要 O(n) 步。

void removeMin(LinkedList<Integer> list) {
    ListIterator<Integer> itList = list.listIterator();

    Integer min = itList.next();

    while(itList.hasNext()) {
        Integer curVal = itList.next();
        if(curVal < min) {
            min = curVal 
            // Copy the iterator here?
        }        
    }
    // remove min from list here.
}

有没有办法在找到新的最小值时复制迭代器，然后我可以调用迭代器的 remove()？

Answer 1

您可以通过这种方式在当前 .next 索引处复制迭代器:

ListIterator<Integer> minItList = List.listIterator(itList.nextIndex());

解决方案如下:

ListIterator<Integer> itList = list.listIterator();
ListIterator<Integer> minItList = list.listIterator();

Integer min = itList.next();

while(itList.hasNext()) {
    Integer curVal = itList.next();
    if(curVal < min) {
        min = curVal; 
        // Copy the iterator here?
        minItList = list.listIterator(itList.nextIndex());
    }        
}
  // remove min from list here.
  minItList.previous();  
  minItList.remove();  //note that you can't call .remove() on list iterator until .next() or .previous() have been called once because you will get IllegalStateException