刪除節點

-4

我有這樣的疑問：給你一個單向鏈表L，其中以L存儲每個節點的整數鍵，以及一個指向L.下一個節點的最後一個節點都有下一個節點設置爲NULL。您將得到一個指針PTR到節點存儲密鑰K，這是不是在列表中的最後一個節點。演示如何從給定ptr的列表中刪除指向包含k的節點的指針k;你的算法應該具有時間複雜度O（1），即它應該與列表的長度無關。假設你有指向L的頭部和尾部節點的指針。我知道，如果我們有一個雙向鏈表，我們可以刪除O（1）時間複雜度的節點，但是我們怎樣才能以單鏈方式清單？我們不需要遍歷所有的列表來找到它之前的節點嗎？刪除節點

來源

2013-11-03 Hussein Hammoud

我想這是一個任務。如果是這樣，不要作弊：查看課程材料，答案將很簡單。這就像3行C代碼，除非你在編寫_you_代碼時遇到_specific_問題，否則我不會給你答案。 –

這是不可能的。 – aschepler

@StefanoSanfilippo首先它不是一個任務，我有一箇中期下週我正在試圖解決一些額外的問題。其次，除非我有一個很艱難的時間試圖解決它，我不會張貼這個問題..這些是我的想法：如果我有一個雙向鏈表，爲了刪除一個指向它的節點的元素，我可以簡單地執行以下操作：ptr-> previous-> next = ptr-> next;但單鏈表中並非如此！ –

考慮 - 「乙 - 」ç - > d爲您的鏈接列表，並讓我們說，我們必須刪除B. 'PTR' 指向B. PTR和PTR之間

交換數據。下一個。現在該列表是A - >Ç - >乙 - > d
化妝ptr.next指向ptr.next.next，使得列表A - >Ç - > d

對於邊緣的情況下，這可能會失敗。如果'ptr'是第一個節點，那麼只需要將頭指向ptr.next即可。但是，如果它是最後一個節點，則不能將尾部移回，所以在這種情況下，您必須遍歷列表並跟蹤前一個節點。

來源

2013-11-03 16:51:53 slider

非常感謝：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

來源

2014-04-03 19:55:05 user3495403

回答

相關問題