c++ - 用O(1)时间循环删除链表？

Question

在一本数据结构书上看到了这个问题，是个思考题，没有给答案。网上找了找，似乎也没有。有没有大神提供个思路？

Answer 1

我同意上面brayden的說法，這個問題在資料結構與演算法上沒有任何意義，應該是樓主看錯題了。問題是O(1)時間刪除循環單鍊錶的某個節點才對，下面簡單給出O(1)時間刪除循環單鍊錶的某個節點的解：
假定要刪除的節點是ListNode *toBeDeleted
要求在O(1)時間內刪除，就肯定不能用遍歷了,由於是單項鍊表，不用遍歷是找不到該節點的前一個節點的，所以就不能用常規鍊錶刪除的方法了。
由於我們知道要刪除的節點ListNode *toBeDeleted，所以我們可以直接得到它的後一個節點ListNode *pNext。我們可以用pNext的內容覆蓋掉toBeDeleted節點，然後將節點toBeDeleted連結到pNext的下一個節點之後將pNext節點刪除即可。以下是一個簡單的示意圖(假設要刪除i)：

原理很簡單就是：完全複製下一個節點，然後在刪除下一個節點，以達到刪除本節點的假象。

Answer 2

之前用過類似的資料結構，沒必要寫什麼記憶體分配函數。主要實現想法如下：

1. 一開始就申請連續的N塊記憶體。每塊記憶體內容為該區塊記憶體是否使用的標記和鍊錶節點資料。
2. 新增節點時在連續的記憶體中找一塊未使用的記憶體區塊，標記為使用。
3. 釋放節點時此區塊記憶體標記為未使用。
4. 刪除鍊錶時釋放掉連續的N塊記憶體即可。
5. 其他如申請的連續記憶體用完之類的問題基本上有解決方法。

但是這樣的做的主要問題是：如果節點是包含資源的，那麼資源必然會洩漏。