Heim > Fragen und Antworten > Hauptteil
ringa_lee2017-04-17 11:22:53
我同意上面brayden的说法,这个问题在数据结构与算法上没有任何意义,应该是楼主看错题了。问题是O(1)时间删除循环单链表的某个节点才对,下面简单给出O(1)时间删除循环单链表的某个节点的解法:
假定要删除的节点是ListNode *toBeDeleted
要求在O(1)时间内删除,就肯定不能用遍历了,由于是单项链表,不用遍历是找不到该节点的前一个节点的,所以就不能用常规链表删除的方法了。
由于我们知道要被删除的节点ListNode *toBeDeleted
,所以我们可以直接得到它的后一个节点ListNode *pNext
。我们可以用pNext
的内容覆盖掉toBeDeleted
节点,然后将节点toBeDeleted
链接到pNext
的下一个节点之后将pNext
节点删除即可。下面是一个简单的示意图(假设要删除i):
原理很简单就是:完全克隆下一个节点,然后在删除下一个节点,以达到删除本节点的假象。
阿神2017-04-17 11:22:53
之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:
但是这样的做的主要问题是:如果节点是包含资源的,那么资源必然会泄露。