反转链表

发布于 2024-12-13 04:34:13 字数 89 浏览 1 评论 0原文

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

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

╰沐子 2024-12-20 04:34:13

的事实

您要求的“更好的方法”可以利用 Java LinkedList 类具有方法addFirst
addLast
removeFirst
removeLast

其中每个都是 O(1)。

您可以通过多种方式获得 O(n) 时间和空间行为。其中一种方法是：

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

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

尽管复制很丑陋，但它的时间复杂度和空间复杂度都是 O(n)。

The "better way" you ask of can exploit the fact that the Java LinkedList class has methods

addFirst
addLast
removeFirst
removeLast

Each of these are O(1).

You can get O(n) time and space behavior in a few ways here. One such way is:

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

This does the reversal "in place" (that is, the variable a references the exact same object at all times). It is equivalent to using a stack as temporary storage (b is the "stack").

It is O(n) time and O(n) space, despite the ugly copying.

回复收藏 0 原文

忘年祭陌 2024-12-20 04:34:13

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

您可能想要使用迭代器（或者更好的 listIterator）。

编辑：此外，您可以通过一些重新排列轻松消除holdPopped。

holdPopped.add 在时间和空间上都是普通的 O(1)，因为您通过传递大小来预分配空间（在空间中是 O(n)）。

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

回复收藏 0 原文

笙痞 2024-12-20 04:34:13

Java API 有一个方法可以在 O(n) 内完成此任务： Collections.reverse(Listlist)。假设这是家庭作业，您应该自己实现它，但在现实生活中您将使用库函数。

或者，您可以创建一个反向装饰器，使反转的时间复杂度为 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 等）。

另外，在此处插入典型的“过早优化是邪恶的”注释 - 如果您的列表实际上是瓶颈，您只会在现实生活中创建此反向出列类。

The Java API has a method for this that completes in O(n): Collections.reverse(List<?> list). Assuming this is homework you should implement this yourself, but in real life you would use the library function.

Alternatively, you can create a reverse decorator which makes the reversal O(1). An example of the concept is below.

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.
}

Note that it is generally (always?) bad form to make a decorator extend a concrete class. Ideally you should implement the public interface and accept a constructor parameter as an instance of the public interface. The above example is purely for illustration purposes, as the LinkedList happens to implement a lot of interfaces (e.g. Dequeue, List etc).

Also, insert the typical "Premature optimisation is evil" comment here - you would only create this reversed dequeue class in real life if your list was actually a bottleneck.

回复收藏 0 原文