Reversing a LinkedList

Question

所以我需要在O(N)时间/空间内反转一个链表。

这个实现是我只使用Java标准库中的LinkedList类(它不允许我访问节点本身)。

Answer 1

您所要求的"更好的方法"可以利用Java LinkedList类具有方法的事实

• addFirst
• addLast
• removeFirst
• removeLast

每一个都是0(1)。

你可以通过几种方式获得O(n)的时间和空间行为。其中一种方法是:

LinkedList<E> b = new LinkedList<E>();
while (!a.isEmpty()) {
    b.addFirst(a.removeFirst());
}
a.addAll(b);

这将"就地"进行反转(即变量a始终引用完全相同的对象)。它相当于使用堆栈作为临时存储(b是"堆栈")。

这是O(n)时间和O(n)空间，尽管丑陋的复制

Answer 2

不，它不是。input.get(idx);本身在时间上就是O(idx)，这使得你的实现在时间上是二次的。

您可能需要使用迭代器(或者更好的是listIterator)。

编辑:此外，你可以很容易地消除holdpop与一些重新排列。

holdPopped.add在时间和空间上都是平凡的0(1)，因为您通过传递大小来预分配空间(在空间上是0 (n))。

IIRC, holdLL.add在时间和空间上也是O(1)平摊。有时会多一些，有时会少一些，但总的空间是n，所以它的平均值应该是O(n)您可以使用holdLL.ensureCapacity来简化分析。

Answer 3

Java API有一个在0 (n)内完成的方法:Collections.reverse(List<?> list)。假设这是作业，您应该自己实现它，但在实际生活中您将使用库函数。

或者，您可以创建一个反向装饰器，使反转为O(1)。下面是这个概念的一个例子。

public class ReversedLinkedList<T> extends LinkedList<T> {
  private final LinkedList<T> list;
  public ReversedLinkedList(LinkedList<T> list) {
    this.list = list;
  }
  public Iterator<T> descendingIterator() {
    return list.iterator();
  }
  public Iterator<T> iterator() {
    return list.descendingIterator();
  }
  public T get(int index) {
    int actualIndex = list.size() - index - 1;
    list.get(actualIndex);
  }
  // Etc.
}

请注意，让装饰器扩展一个具体类通常(总是?)是不好的形式。理想情况下，您应该实现公共接口并接受构造函数参数作为公共接口的实例。上面的例子纯粹是为了说明目的，因为LinkedList碰巧实现了很多接口(例如Dequeue, List等)。

另外，在这里插入典型的"过早优化是邪恶的"注释——只有当你的列表实际上是一个瓶颈时，你才会在现实生活中创建这个反向dequeue类。

Answer 4

你应该经常检查apache commons，它们对于linkedlist和集合有更好更灵活的实现;

https://commons.apache.org

其次，如果你想反转一个列表，使用双链表会更容易。