Heim  >  Fragen und Antworten  >  Hauptteil

c++ - 用O(1)时间循环删除链表?

在一本数据结构书上看到了这个问题,是个思考题,没有给答案。网上找了找,似乎也没有。有没有大神提供个思路?

伊谢尔伦伊谢尔伦2765 Tage vor630

Antworte allen(2)Ich werde antworten

  • ringa_lee

    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):

    原理很简单就是:完全克隆下一个节点,然后在删除下一个节点,以达到删除本节点的假象。

    Antwort
    0
  • 阿神

    阿神2017-04-17 11:22:53

    之前用过类似的数据结构,没必要写什么内存分配函数。主要实现思路如下:

    1. 一开始就申请连续的N块内存。每块内存内容为该块内存是否使用的标记和链表节点数据。
    2. 添加节点时在连续的内存中找一块未使用的内存块,标记为使用。
    3. 释放节点时该块内存标记为未使用。
    4. 删除链表时释放掉连续的N块内存即可。
    5. 其他如申请的连续内存用完之类的问题基本有解决方法。

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

    Antwort
    0
  • StornierenAntwort