佚名通过本文主要向大家介绍了o1-苏州瑞友钢铁,o1签证材料,美国o1签证,o1,联想o1游戏等相关知识,希望对您有所帮助,也希望大家支持linkedu.com www.linkedu.com
问题：用O1时间循环删除链表？
描述:
解决方案1:
描述:
在一本数据结构书上看到了这个问题，是个思考题，没有给答案。网上找了找，似乎也没有。有没有大神提供个思路？
解决方案1:
之前用过类似的数据结构，没必要写什么内存分配函数。主要实现思路如下：
- 一开始就申请连续的N块内存。每块内存内容为该块内存是否使用的标记和链表节点数据。
- 添加节点时在连续的内存中找一块未使用的内存块，标记为使用。
- 释放节点时该块内存标记为未使用。
- 删除链表时释放掉连续的N块内存即可。
- 其他如申请的连续内存用完之类的问题基本有解决方法。
但是这样的做的主要问题是：如果节点是包含资源的，那么资源必然会泄露。
解决方案2:我同意上面brayden的说法，这个问题在数据结构与算法上没有任何意义，应该是楼主看错题了。问题是O(1)时间删除循环单链表的某个节点才对，下面简单给出O(1)时间删除循环单链表的某个节点的解法：
假定要删除的节点是ListNode *toBeDeleted
要求在O(1)时间内删除，就肯定不能用遍历了,由于是单项链表，不用遍历是找不到该节点的前一个节点的，所以就不能用常规链表删除的方法了。
由于我们知道要被删除的节点ListNode *toBeDeleted，所以我们可以直接得到它的后一个节点ListNode *pNext。我们可以用pNext的内容覆盖掉toBeDeleted节点，然后将节点toBeDeleted链接到pNext的下一个节点之后将pNext节点删除即可。下面是一个简单的示意图(假设要删除i)：
原理很简单就是：完全克隆下一个节点，然后在删除下一个节点，以达到删除本节点的假象。