关于链表删除操作O(1)时间复杂度的实现困惑求解

先明确课本结论的前提 #

课本说链表插入/删除时间复杂度为O(1)，是在已持有操作节点的直接关联节点指针的前提下：

• 删除：持有要删除节点的前驱指针；
• 插入：持有要插入位置的前驱（或后继）指针。
  如果没有这个前提，单链表确实无法做到O(1)，这是单链表的结构特性决定的。

解决你困惑的几种可行方案 #

1. 改用双向链表

这是最直接的解决方案，给每个节点增加一个prev指针指向前驱节点：

• 删除指定节点时，直接通过position->prev找到前驱，修改前驱的next为position->next，同时修改后继的prev为position->prev，最后释放节点，全程O(1)；
• 插入节点时，无论在指定节点前还是后，只要持有该节点指针，直接调整prev和next指针即可，时间复杂度O(1)。
  缺点是每个节点多占用一个指针的内存，实现逻辑比单链表稍复杂，但彻底解决了前驱查找的问题。

2. 保留单链表，优化删除逻辑（接受规则约束）

你贴的那种“偷梁换柱”式O(1)删除方法，核心是把后继节点的内容复制到当前节点，再删除后继节点。要解决后继节点引用失效的问题，只需要在业务代码中遵守操作约定：

• 删除操作返回的指针是原节点的位置（此时原节点已经承载了后继节点的内容），后续所有对该位置节点的操作，必须使用返回的指针，不能再使用原来指向后继节点的引用；
• 如果你的业务场景中不会单独持有链表节点的引用（比如只通过链表头遍历访问，不会保存某个节点的指针），这个方法完全可以安全使用。

3. 针对插入操作的O(1)实现

单链表本身在两种场景下插入就是O(1)：

• 在链表头部插入：直接创建新节点，让新节点的next指向头节点，再更新头指针；
• 在指定节点后插入：只要持有该节点的指针，直接让新节点的next指向该节点的next，再把该节点的next指向新节点。
  如果需要在指定节点前插入，单链表本身做不到O(1)，但可以用类似删除的“偷梁换柱”技巧：

1. 创建新节点，把指定节点的值复制到新节点；
2. 将指定节点的值替换为要插入的新值；
3. 把新节点插入到指定节点的后面。
   这样从外部看，就像是在指定节点前插入了新节点，时间复杂度O(1)，同样需要注意原节点引用的一致性问题。

补充你的代码示例说明 #

你给出的代码中：

• 前两种erase方法需要遍历链表找到目标节点的前驱，因此时间复杂度为O(n)：

// 这些操作需要找到目标位置的前驱节点，因此时间复杂度为O(n)。
node* erase(node* head, int pos);
node* erase(node* node_to_delete);

• 第三种方法通过复制后继节点实现了O(1)删除，但会导致原后继节点的引用失效，需要通过操作约定来规避风险：

// 此操作时间复杂度为O(1)，但会影响后继节点引用的有效性。
node* erase(node* position) {
    if (position == _last)
        return _last;
    auto tmp = position -> next;
    position -> val = position -> next -> val;
    position -> next = position -> next -> next;
    delete tmp;
    if (tmp == _last) 
        _last = position;
    _size--;
    return position;
}

内容的提问来源于stack exchange，提问作者Zeelok Chan