反向鏈接列表

所以我需要在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

反向鏈接列表

回答

相關問題