链表删除节点的时间复杂度是多少及其详细分析

核心结论：四大场景复杂度矩阵

为了建立直观认知，我们首先明确不同输入条件下的时间开销分布。链表操作的耗时通常分为两部分：“定位开销”与“指针重连（断链）开销”。

场景一：按数值或索引删除（标准遍历删除）

最常规的需求是“从链表中删除值为 X 的节点”或“删除第 k 个节点”。因为单链表和双向链表在物理存储上都是离散分布的，不支持数组那样的 O(1) 常数级下标寻址，程序必须维护一个工作指针从头节点开始沿指针链向后推进。

在遍历过程中，最理想的情况是首个节点即为目标节点（最好情况 O(1)）；最差情况是目标节点位于链表尾部或根本不存在（最坏情况 O(n)）。在计算算法复杂度时，我们关注其平均及最坏情况，因此查找耗时为 O(n)。一旦定位到对应位置，修改指针使其绕开目标节点的操作仅需常数步运算（O(1)）。综合两部分，总时间复杂度为 O(n)。

图 1：单链表按值查找并删除节点的执行结构与时间开销分布

场景二：已知待删节点指针，单链表常规删除为何仍是 O(n)？

很多初学者容易在此产生误解：“既然都已经直接给我目标节点的内存指针了，删除不就是把指针断开吗，为什么还会是 O(n)？”

问题的根本症结在于单向链表的物理指针单向性。在单链表中，每个节点只保存指向其后继节点（next）的地址，并不保存其前驱节点（prev）的地址。要想在物理链路上剔除节点 target，必须让 target 的前驱节点直接指向 target 的后继节点：

prev->next = target->next;

但此时调用者手中仅有 target 指针，根本不知道 prev 位于何处。为了拿到 prev，程序必须回退到整个链表的根部 head，执行一次全链遍历：当 curr->next == target 时，才算找齐了执行删除所需的全部句柄。这次重走链表的开销，直接将整个操作拖入了 O(n) 的时间复杂度。

场景三：常数级破局——已知指针下的特殊解法与双向链表

1. 单链表的值覆盖法（复制后继节点，理论 O(1)）

若调用接口只给定了 target 指针，且没有给定头指针，算法领域存在一个巧妙的“李代桃僵”解法：将后继节点的数据复制到当前节点，然后删除后继节点。

图 2：单链表通过“伪装覆盖”达到 O(1) 删除的核心推导机制

2. 双向链表（Doubly Linked List）的原生 O(1) 实现

双向链表通过每个节点内部额外维护的 prev 前驱指针，彻底解决了物理层面的不可逆问题。当给定待删除节点指针 node 时，无论该节点处于链表何处（头、中、尾），都可以在 O(1) 时间内直接完成前驱与后继的双向握手：

图 3：双向链表通过自包含的前驱/后继指针直接完成 O(1) 脱链

完整代码实现与实操验证

下面给出一段标准的 C++ 示例代码，直观展示上述各种删除逻辑在工程实现中的不同特征与耗时差异：

#include 

// 1. 单链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 2. 双向链表节点定义
struct DListNode {
    int val;
    DListNode* prev;
    DListNode* next;
    DListNode(int x) : val(x), prev(nullptr), next(nullptr) {}
};

// 单链表常规删除：必须依赖头指针，O(n)
ListNode* deleteByValue(ListNode* head, int targetVal) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode* prev = &dummy;
    
    // 线性扫描查找前驱节点：耗时 O(n)
    while (prev->next != nullptr && prev->next->val != targetVal) {
        prev = prev->next;
    }
    
    if (prev->next != nullptr) {
        ListNode* toDelete = prev->next;
        prev->next = toDelete->next; // 断链 O(1)
        delete toDelete;
    }
    return dummy.next;
}

// 单链表快速删除：给定已知节点，值复制覆盖，O(1)
bool deleteNodeFastO1(ListNode* target) {
    // 尾节点无法用此法
    if (target == nullptr || target->next == nullptr) {
        return false;
    }
    ListNode* nextNode = target->next;
    target->val = nextNode->val;        // 复制后继值
    target->next = nextNode->next;      // 跳过后继节点
    delete nextNode;
    return true;
}

// 双向链表已知节点删除：原生 O(1)
void deleteDListNode(DListNode*& head, DListNode* target) {
    if (!target) return;

    if (target->prev != nullptr) {
        target->prev->next = target->next;
    } else {
        head = target->next; // 删除了头节点
    }

    if (target->next != nullptr) {
        target->next->prev = target->prev;
    }

    delete target;
}

决策模型总结

在工程设计或技术面试中面对“链表删除复杂度”这一问题时，可以借助如下推导决策流来确定准确的评估路径：

图 4：链表删除操作复杂度决策分析模型

最终总结：

不要脱离上下文单独评判数据结构操作的优劣。链表常被称赞为“具备 O(1) 的插入和删除性能”，这一结论成立的充要条件是“已经持有操作位置的直接指针引用（并且能访问到前驱）”。一旦需要依赖“数值查找”或“基于序号的检索”，由于链表无法建立索引映射，查找阶段不可避免地耗费 O(n) 时间，此时删除节点的总执行耗时仍然是 O(n)。