84669 Lernen von Personen
152542 Lernen von Personen
20005 Lernen von Personen
5487 Lernen von Personen
7821 Lernen von Personen
359900 Lernen von Personen
3350 Lernen von Personen
180660 Lernen von Personen
48569 Lernen von Personen
18603 Lernen von Personen
40936 Lernen von Personen
1549 Lernen von Personen
1183 Lernen von Personen
32909 Lernen von Personen
在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?
小伙看你根骨奇佳,潜力无限,来学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):之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:
但是这样的做的主要问题是:如果节点是包含资源的,那么资源必然会泄露。