反向链接列表

所以我需要在O（N）时间/空间中反转链接列表。反向链接列表

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

来源

2011-11-01 mango

由于原始代码位于外部网站（请参阅编辑历史记录）并且不再可用，因此我正在投票以关闭此题目作为题目。 –

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

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

编辑：此外，你可以很容易地消除holdPopped与一个小重新安排。

holdPopped.add由于您通过传递大小预先分配空间（即在空间中为O（n）），所以在时间和空间上都将平均为O（1）。

IIRC，holdLL.add也在时间和空间上摊销O（1）。有时它会更多，有时更少，但总空间是n，所以它应该平均到O（n）。您可以使用holdLL.ensureCapacity简化分析。

来源

2011-11-01 04:39:11

ahhhhh我明白了，谢谢你的支持！所以我应该最好使用迭代器。我会解决它，再次感谢。 – mango

我更新了我的方法，并将其添加到了holdLL.ensureCapacity中（未在更新的pastebin链接中显示），我真的不知道该方法，这非常酷！我认为应该是O（N）时间/空间现在 – mango

的 “更好的方式” 你问的可以利用的事实，在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）空间，尽管丑陋的复制。

来源

2011-11-01 04:47:52

嘿非常感谢！我改变它以利用O（1）方法。我需要将它反转，所以我改了一点算法。我觉得可以通过保持堆栈的实现来消除来回复制。 – mango

不应该是removeFirst和AddFirst来逆转列表，因为removeLast和addFirst会简单地复制列表（因为这些操作保留了排序）？ –

谢谢@马克你是绝对正确的！我借此机会清理答案并使用真实代码。当我给出第一个回答#shameonme时，我应该测试它。 –

Java API有一个完成O（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等）。

此外，在这里插入典型的“过早优化是邪恶的”评论 - 如果您的列表实际上是一个瓶颈，那么您只能在现实生活中创建这个反向排队类。

来源

2011-11-01 05:53:13 Bringer128

http://www.docjar.com/html/api/java/util/Collections.java.html中的第412-435行，如果您想了解JDK实现者如何实现它的话。 –

您应经常检查阿帕奇百科全书，他们对于LinkedList的和收藏一般更好，更灵活的实现;

https://commons.apache.org

其次，它会更容易为你，如果你想扭转列表中使用双向链表。

来源

2016-03-12 23:01:45

反向链接列表

回答

相关问题