GESP 五级 · GESP 202603 C++ 五级 第 1 题

关于单链表、双链表和循环链表，下列说法正确的是（ ）。

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

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

【考点】指针操作｜时间复杂度｜链表判空

---

🎯 考纲定位

本题出自《GESP 五年级 C++ 考试大纲》第 3 部分"数据结构基础"中"链表"模块。命题人把这道题放在五级，不是随便考考指针——它精准卡住的是指针操作与链表判空这两个互相关联却极易混淆的知识点。绝大多数考生在这里栽跟头，是因为没把"指针指向的逻辑关系"和"时间复杂度"分开想。

---

🧠 解题思维

看到链表题，先想指针关系：单链表只有后继指针，删任意结点必须知道前驱才能改指针，所以 O(1) 删除是假的；循环链表头尾相接，尾的 next 一定指回头，不是空指针；带头结点的循环单链表里，只有头结点的 next 指向自己时，链表才真的没结点。

通法：链表问题拆解三步——①先画任意结点的指针关系图，②再看操作需要哪些指针参与，③最后数需要遍历几跳。按这个流程，删结点是否 O(1)、判空条件是什么，一眼就出来了。

---

🪤 陷阱拆解

A 项的"O(1) 删除任意结点"是命题人最爱的偷换概念——它默认你手里已经拿着前驱指针，但题目只说"已知任意结点的指针"，单链表里没了前驱就得从头找，复杂度立刻掉到 O(n)。

B 项"循环链表一定不存在空指针"说的是单向循环链表成立，但题干把双链表也混进来，双链表头结点既有 next 也有 prev，尾结点 prev 指头，next 指头，确实没空指针——命题人就是利用考生对"循环链表"默认只想到单向的经验盲区。

C 项更阴险，"尾结点 next 一定为 nullptr"把循环链表的定义和普通链表偷换了，循环链表里尾的 next 指头，头不是空指针，所以 C 错得特别隐蔽。

D 项是唯一把带头结点这个前提和循环单链表的判空条件结合正确的选项。

---

🔄 反命题思维

命题人如果把这题改个条件——比如"在带头结点的循环双链表中，判定是否为空只需判断头结点的 next 是否指向自身"，答案就变成 false，因为双链表头结点的 prev 也指自身才是空。

刷到类似题，先别急着选，问自己一句：这题考的是指针关系还是时间复杂度？有没有默认前提被我偷换了？ 问清楚，陷阱就自己跳出来了。