我有這樣的疑問： 給你一個單向鏈表L，其中以L存儲每個節點的整數鍵，以及一個指向L.下一個節點的最後一個節點都有下一個節點設置爲NULL。 您將得到一個指針PTR到節點存儲密鑰K，這是不是在列表中的最後一個節點。 演示如何從給定ptr的列表中刪除指向包含k的節點的指針k;你的算法應該具有時間複雜度O（1），即它應該與列表的長度無關。假設你有指向L的頭部和尾部節點的指針。我知道，如果我們有一個雙向鏈表，我們可以刪除O（1）時間複雜度的節點，但是我們怎樣才能以單鏈方式清單？ 我們不需要遍歷所有的列表來找到它之前的節點嗎？刪除節點
考慮 - 「乙 - 」ç - > d爲您的鏈接列表，並讓我們說，我們必須刪除B. 'PTR' 指向B. PTR和PTR之間
對於邊緣的情況下，這可能會失敗。如果'ptr'是第一個節點，那麼只需要將頭指向ptr.next即可。但是，如果它是最後一個節點，則不能將尾部移回，所以在這種情況下，您必須遍歷列表並跟蹤前一個節點。
非常感謝：D它非常清楚和有用:) –
我知道如何做到這一點的棧（LIFO） - 插入/刪除與O（1）
如果你不介意的話，這些數據將是倒退，那麼你可以添加最後一個項目喜歡第一。
例子： list.insert(1)
list.insert(2)
list.insert(3)
以常規方式將在列表如下：(1,2,3) 但如果你需要O（1）則會是這樣的：(3,2,1) - 然後是最後一個項目將在第1位，所以刪除會是這樣的（Ruby代碼）
def delete
@head = @head.next
end
我想這是一個任務。如果是這樣，不要作弊：查看課程材料，答案將很簡單。這就像3行C代碼，除非你在編寫_you_代碼時遇到_specific_問題，否則我不會給你答案。 –
這是不可能的。 – aschepler
@StefanoSanfilippo首先它不是一個任務，我有一箇中期下週我正在試圖解決一些額外的問題。其次，除非我有一個很艱難的時間試圖解決它，我不會張貼這個問題..這些是我的想法：如果我有一個雙向鏈表，爲了刪除一個指向它的節點的元素，我可以簡單地執行以下操作：ptr-> previous-> next = ptr-> next;但單鏈表中並非如此！ –