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. 其他如申请的连续内存用完之类的问题基本有解决方法。

但是这样的做的主要问题是：如果节点是包含资源的，那么资源必然会泄露。