面试题18（一）：在O(1)时间删除链表节点

从“给了目标指针却没有前驱”开始

先预测：单向链表1→2→3→4→5中只给头指针和节点3的指针。普通删除要把节点2的next改成4，但节点3没有指向2的反向链接；不从头扫描，怎样找到并修改前驱？

只能向后访问。题目“在O(1)时间删除链表节点”的突破口不是凭空获得，而是对非尾节点改变“究竟删除哪个物理对象”。

已知目标节点target还有后继next时，先复制下一个节点内容到target，再令target->next = next->next并释放next。从链表值序列看，目标原值消失了；所有动作都只访问目标和后继，时间O(1)。

常数时间删除的是逻辑值，不是目标对象

这种做法属于。目标对象地址仍在链表中，只是内容从3变成4；真正被delete的是原来值4的后继对象。

因此算法保证的是“删除后链表值序列与移除目标位置一致”，不保证传入的target对象被销毁。如果节点只承载普通整数且没有外部身份观察，这个替换不可见；若地址、唯一ID、锁、文件句柄、引用计数或析构副作用有业务意义，语义就不再等价。

发生两种变化：持有target的外部指针仍有效，但看到的值改变；持有target->next原后继的外部指针在删除后悬空。接口必须明确链表节点是否允许外部长期引用。

尾节点为何仍要顺序查找

尾节点next为空，没有后继内容可复制，也没有可绕过的后继对象。要让链表不再指向它，必须修改前驱的next；在单向链表中只能从头沿链查找，时间O(n)。因此“尾节点需要顺序查找”是不可省略的特例。

若链表只有一个节点，目标同时是头和尾，不需要扫描前驱：释放目标并把头指针设为空即可。若删除多节点链表的头，头不是尾，可走常数分支：把第二个节点内容复制到头并释放第二个对象，头地址保持不变。

作者接收ListNode** pListHead，因为单节点删除会改变调用者持有的头指针。现代 C++ 也可使用ListNode*& head；若只按值传ListNode* head，函数把本地变量设为空不会更新调用者。

忠实实现三个删除分支

下面保留作者的裸指针结构，并把返回值改成布尔状态。它仍有一个核心前置条件：target必须属于head所指链表。非尾分支若先做线性归属验证，就会失去O(1)优势。

struct ListNode {
    int value;
    ListNode* next = nullptr;
};
 
bool deleteKnownNode(ListNode*& head, ListNode* target) {
    if (head == nullptr || target == nullptr) return false;
 
    if (target->next != nullptr) {
        ListNode* successor = target->next;
        target->value = successor->value;
        target->next = successor->next;
        delete successor;
        return true;
    }
 
    if (head == target) {
        delete target;
        head = nullptr;
        return true;
    }
 
    ListNode* predecessor = head;
    while (predecessor != nullptr &&
           predecessor->next != target) {
        predecessor = predecessor->next;
    }
    if (predecessor == nullptr) return false;
 
    predecessor->next = nullptr;
    delete target;
    return true;
}

尾分支循环加入predecessor != nullptr检查，避免不属于链表的尾目标让程序解引用空指针。但非尾外部目标仍可能有自己的后继，函数会错误修改并释放外部结构；“已知属于链表”必须是可信调用契约，或由更高层句柄系统保证。

若必须接受不可信裸指针，先从头验证归属再删除，所有情况最坏O(n)。工程 API 可以不暴露节点指针，改用迭代器/句柄由容器验证版本与所有者，或让调用方同时提供前驱指针；复杂度、易用性与安全性需要明确取舍。

平均 O(1) 不是每次 O(1)（均摊复杂度）

长度n链表有n-1个非尾节点可常数删除，只有一个尾节点需要O(n)扫描。若目标在所有节点中等概率随机选择，一次删除期望代价约为：

((n-1)·O(1) + O(n)) / n = O(1)。

这就是书中“平均时间复杂度O(1)”的结论。它是对目标分布的平均分析，不是摊还分析，也不是单次最坏保证。若业务总删除尾节点，每次仍是O(n)；不能用平均结论掩盖特定工作负载。

依赖等概率或相近分布假设。摊还复杂度则不要求概率，分析任意操作序列的总代价；两者概念不同。

值复制与异常安全限制

作者节点值是int，赋值不会抛异常。泛型节点若保存std::string、资源对象或不可复制类型，target->value = successor->value可能昂贵、抛异常或根本无法编译。算法的“常数节点访问”不代表值复制成本一定O(1)。

若赋值抛出但目标值部分改变，链表可能仍连接却内容损坏。可先构造临时值，再用无异常交换提交，但类型仍需提供合适保证；移动后继值可能让异常前的后继处于已移动状态。容器通用实现通常不会用这种技巧提供强异常保证。

以下unique_ptr版本能让后继释放自动发生，但仍改变目标身份并要求值可赋值：

#include <memory>
 
struct OwnedNode {
    int value;
    std::unique_ptr<OwnedNode> next;
};
 
bool deleteNonTail(OwnedNode* target) {
    if (target == nullptr || target->next == nullptr) return false;
    target->value = target->next->value;
    target->next = std::move(target->next->next);
    return true;
}
 
bool deleteTail(std::unique_ptr<OwnedNode>& head,
                OwnedNode* target) {
    auto* link = &head;
    while (*link != nullptr && link->get() != target) {
        link = &((*link)->next);
    }
    if (*link == nullptr) return false;
    *link = std::move((*link)->next);
    return true;
}

link指向拥有当前节点的unique_ptr，找到目标后把它替换为其后继即可；这种“指向链接的指针”还能统一删除头与其他节点。若目标是尾，仍需从头遍历所有权链。

并发、迭代器与外部观察者

在另一个线程可能遍历或修改链表时，复制值、改指针和释放节点不是原子事务。读线程可能看到新值与旧后继组合，或访问已释放后继。必须使用锁、读复制更新、危险指针等并发回收机制；算法题裸指针版本不是线程安全容器。

即使单线程，指向后继的迭代器会失效，指向目标的迭代器继续有效但元素值改变。这与标准容器通常描述的失效规则不同。若调用方依赖“只使被删节点迭代器失效”，本技巧违背预期。

节点包含从值派生的缓存字段时，复制主值后也要同步更新所有不变量。只复制value而遗漏哈希、时间戳或索引键，会留下内部不一致。安全前提不只是“值可复制”，还包括“完整逻辑内容可替换”。

怎样获得真正任意节点最坏 O(1)

若每个节点同时保存prev和next，双向链表可直接让target->prev->next与target->next->prev互相连接，再释放target；头尾通过哨兵或边界分支处理，任意已知节点物理删除都是最坏O(1)。代价是每节点多一个指针，插入删除要维护更多不变量。

单向链表也可让删除 API 同时接收前驱与目标，或让迭代器内部持有“指向当前链接的指针”。调用方若已经在遍历中拥有前驱，删除就是常数；若只有目标，寻找前驱的成本只是被移到调用方，整体仍可能线性。

尾指针只能让访问尾节点为O(1)，不能让单向尾删除变快，因为仍不知道倒数第二个节点。维护尾指针与前驱缓存、哈希映射或数组索引都能增加信息，但更新每次链表变更的成本和一致性风险也要计入。

使用哨兵头节点可以统一“删除真实头”和普通节点的链接操作，却仍不能从目标反向找到前驱。哨兵减少边界分支，不改变信息可达性；不能把代码更短误解为复杂度更低。

所以题目的技巧是在不改数据结构、只给目标指针的限制下，用身份替换覆盖n-1个非尾位置。若需求明确要求销毁目标物理对象，应选择双向链表或提供前驱，而不是继续包装复制后继方案。

按值删除与按节点删除是不同接口

若调用方只给一个值3而不是节点指针，函数还要从头查找匹配节点，时间已经是O(n)；存在重复值时还要约定删第一个、全部还是指定身份。本题常数技巧依赖调用者已经拥有准确节点地址。

若节点句柄可能过期，可为容器分配所有者ID和版本号，删除前校验句柄仍属于当前链表。裸指针无法在对象释放后安全读取这些元数据；句柄表或代际索引能检测陈旧引用，但增加一次间接访问。

返回状态也应区分空输入、目标不属于链表、已删除和不支持身份替换。单一bool足够演示，却无法告诉调用方失败原因；生产接口可使用枚举错误，并在调试构建中做线性归属验证。

当复制技巧与普通物理删除都可用时，API 不应根据节点位置悄悄改变外部失效规则。可以明确命名eraseValueAtKnownNode，或始终走普通删除保持统一身份语义；可预测性往往比少一次线性扫描更重要。

用内存工具验证释放对象

测试值序列只能发现链接错误，不能发现重复释放、泄漏或悬空访问。地址消毒器能捕获删除后解引用原后继，泄漏检测能发现尾分支未释放；未定义行为检测器可暴露无效指针运算。测试结束还要销毁剩余链表，避免夹具自身泄漏干扰结果。

调试分配器可在释放对象上填充特殊模式，使“代码看似还能读取旧值”的悬空错误更快暴露。绝不能以一次运行中已删除地址仍显示4作为安全证据；释放后对象生命周期已经结束，任何解引用都无定义。

若链表可能有环，常规销毁与尾查找都可能不终止。题目假设无环单向链表；接收外部结构时可先检测环或由容器封装保证，不能让删除函数同时承担所有结构修复责任。

官方五类测试与身份断言

作者构造1→2→3→4→5，分别删除中间3、尾5、头1；再测试单节点删除和空链表。预期逻辑序列分别为1,2,4,5、1,2,3,4、2,3,4,5、空、空。

自动测试还应记录地址：删除中间3后原target地址仍在链表，值变4；原后继地址不再可用。不要解引用已删除指针，可在删除前保存地址数值，仅比较链表当前节点地址集合中不再包含它。

#include <cassert>
#include <vector>
 
std::vector<int> values(const ListNode* head) {
    std::vector<int> result;
    for (auto* node = head; node != nullptr; node = node->next) {
        result.push_back(node->value);
    }
    return result;
}
 
void testDeleteNode() {
    auto* n1 = new ListNode{1};
    auto* n2 = new ListNode{2};
    auto* n3 = new ListNode{3};
    auto* n4 = new ListNode{4};
    auto* n5 = new ListNode{5};
    n1->next=n2; n2->next=n3; n3->next=n4; n4->next=n5;
 
    ListNode* head = n1;
    assert(deleteKnownNode(head, n3));
    assert((values(head) == std::vector<int>{1,2,4,5}));
    assert(n3->value == 4);
 
    assert(deleteKnownNode(head, n5));
    assert((values(head) == std::vector<int>{1,2,4}));
 
    assert(deleteKnownNode(head, head));
    assert((values(head) == std::vector<int>{2,4}));
}

测试代码要按当前链表销毁剩余节点，避免把算法正确性与测试泄漏混在一起。还应覆盖空目标、目标不属于链表的尾节点、单节点头删除，以及带自引用或环的非法链表；后两类需由契约拒绝，否则顺序查找可能不终止。

本章练习

本章回顾

1. 在O(1)时间删除链表节点只对有后继的目标成立。
2. 非尾分支复制下一个节点内容，绕过并释放后继对象。
3. 该技巧实现逻辑删除，target物理地址保留、后继物理对象被销毁。
4. 尾节点需要顺序查找前驱，多节点尾删除最坏O(n)。
5. 单节点删除必须更新调用者头指针，因此入口需传头指针引用或二级指针。
6. 等概率目标假设下平均时间复杂度O(1)，但特定尾删除工作负载仍是线性。
7. 目标必须属于链表，节点值必须允许完整、异常安全地替换。
8. 外部引用、节点身份、并发回收或不可复制资源存在时，应使用普通前驱删除。

名词解释