反向链接列表

Question

因此，我需要反转O（N）时间/空间中的链表。

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

Answer 1

您要求的“更好的方式”可以利用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）时间和O（n）空间。