GESP 五级 · GESP 202512 C++ 五级 第 3 题

下面关于单链表和双链表的描述中，正确的是（ ）。

struct DNode {
    int data;
    DNode* prev;
    DNode* next;
};

// 在双链表中删除指定节点
void deleteNode(DNode* node) {
    if (node->prev) {
        node->prev->next = node->next;
    }
    if (node->next) {
        node->next->prev = node->prev;
    }
    delete node;
}

struct SNode {
    int data;
    SNode* next;
};

// 在单链表中删除指定节点
void deleteSNode(SNode* head, SNode* node) {
    SNode* prev = head;
    while (prev->next != node) {
        prev = prev->next;
    }
    prev->next = node->next;
    delete node;
}

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】链表操作｜时间复杂度分析｜指针语义理解

这道题考的是链表删除的时间复杂度，核心在于区分"有指针"和"无指针"两种场景。

1. 🎯 考纲定位

GESP五级链表模块核心考点。命题人卡住的是学生混淆了"有指针"和"无指针"两种删除场景——双链表删除给定节点是O(1)，单链表删除给定节点是O(n)。这个陷阱在五级试卷中高频出现，因为学生容易凭直觉认为"删除就是O(1)"。

2. 🧠 解题思维

先看双链表：deleteNode的参数直接是目标节点指针，prev/next字段全程可见，代码里只改两个指针引用，常数时间搞定。再看单链表：deleteSNode只传头指针和目标节点，必须从头遍历找前驱，循环次数与链表长度线性相关，所以是O(n)。时间复杂度看的是最坏情况，不是平均情况。

3. 🪤 陷阱拆解

A错在把双链表误判为O(n)——它忽略了双链表可直接访问前驱的特性。B错在把单链表误判为O(1)——它忽略了单链表必须找前驱的遍历开销。D错在把两者都判为O(n)——它忽略了双链表删除的常数时间优势。这些错误选项都是利用学生对链表删除操作的直觉理解偏差设计的。

4. 🔄 反命题思维

若把单链表deleteSNode的参数改成只传目标节点（无头指针），复杂度仍是O(n)；若把双链表deleteNode的参数改成只传节点指针但禁止访问prev/next，复杂度会退化到O(n)。刷到链表删除题时，先问自己"题目给的是节点指针还是头指针"。