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

在单链表中，已知指针 $ p $ 指向要删除的结点（非尾结点），想在 $ O(1) $ 删除 $ p $，可行做法是用 p->next 覆盖 $ p $ 的值与 $ next $，然后删除 p->next。

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

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

1. 🎯 考纲定位（考点定位）

单链表删除通常需前驱指针，但五级命题人偏爱考空间换时间的特例：若允许用 O(1) 删除非尾结点，直接复制后继值覆盖当前结点，再释放后继，即可绕过前驱查找。

2. 🧠 解题思维（拆解与通法）

核心观察是"删除操作本质是切断链表连接"，而非"擦除节点值"。当 p 非尾结点时，p->next 一定存在；用 p->next 覆盖 p->val 和 p->next 后，原 p 节点虽仍占内存，但它在链表中已无引用，逻辑上等同于被删除。