84669 orang belajar
152542 orang belajar
20005 orang belajar
5487 orang belajar
7821 orang belajar
359900 orang belajar
3350 orang belajar
180660 orang belajar
48569 orang belajar
18603 orang belajar
40936 orang belajar
1549 orang belajar
1183 orang belajar
32909 orang belajar
在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?
小伙看你根骨奇佳,潜力无限,来学PHP伐。
我同意上面brayden的说法,这个问题在数据结构与算法上没有任何意义,应该是楼主看错题了。问题是O(1)时间删除循环单链表的某个节点才对,下面简单给出O(1)时间删除循环单链表的某个节点的解法: 假定要删除的节点是ListNode *toBeDeleted 要求在O(1)时间内删除,就肯定不能用遍历了,由于是单项链表,不用遍历是找不到该节点的前一个节点的,所以就不能用常规链表删除的方法了。 由于我们知道要被删除的节点ListNode *toBeDeleted,所以我们可以直接得到它的后一个节点ListNode *pNext。我们可以用pNext的内容覆盖掉toBeDeleted节点,然后将节点toBeDeleted链接到pNext的下一个节点之后将pNext节点删除即可。下面是一个简单的示意图(假设要删除i):
ListNode *toBeDeleted
ListNode *pNext
pNext
toBeDeleted
原理很简单就是:完全克隆下一个节点,然后在删除下一个节点,以达到删除本节点的假象。
之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:
但是这样的做的主要问题是:如果节点是包含资源的,那么资源必然会泄露。
我同意上面brayden的说法,这个问题在数据结构与算法上没有任何意义,应该是楼主看错题了。问题是O(1)时间删除循环单链表的某个节点才对,下面简单给出O(1)时间删除循环单链表的某个节点的解法:
假定要删除的节点是
ListNode *toBeDeleted
要求在O(1)时间内删除,就肯定不能用遍历了,由于是单项链表,不用遍历是找不到该节点的前一个节点的,所以就不能用常规链表删除的方法了。
由于我们知道要被删除的节点
ListNode *toBeDeleted
,所以我们可以直接得到它的后一个节点ListNode *pNext
。我们可以用pNext
的内容覆盖掉toBeDeleted
节点,然后将节点toBeDeleted
链接到pNext
的下一个节点之后将pNext
节点删除即可。下面是一个简单的示意图(假设要删除i):之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:
但是这样的做的主要问题是:如果节点是包含资源的,那么资源必然会泄露。