GESP 七级 · GESP 202603 C++ 七级 第 14 题

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

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

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

【考点】循环链表结构｜带头结点判空｜指针语义

命题人卡在考生对"循环链表头部特殊性"的模糊认知上。GESP 七级明确要求掌握带头结点的循环链表实现，而本题正是对"空链表判定条件"的精准考查——绝大多数考生只记得"头指针是否为NULL"，却忽略了循环链表头结点next自指这一关键结构特征，导致误选其他选项。

先看D项：带头结点的循环单链表，若链表为空，头结点next必然指向自身（因为无数据结点可指向）；若链表非空，头结点next指向第一个数据结点，二者不相等。因此仅判断head->next == head即可判定为空，D项正确。

A项易错：单链表删除结点必须已知前驱指针才能修改前驱的next，仅知道被删结点指针时，仍需从头遍历找前驱，时间复杂度为O(n)，非O(1)。

B项陷阱：循环链表"无空指针"是相对数据结点而言，但头指针本身仍是指针，空链表时头指针为NULL，B项表述绝对化。

C项错误：循环双链表中尾结点next应指向头结点，而非NULL，混淆了线性与循环结构。

命题人故意用"一定不存在空指针""尾结点next一定为NULL"等绝对化表述制造认知冲突。A项利用了"删除操作O(1)是常见结论"的思维定势，却忽略了单链表单向性的本质限制。C项则利用双链表对称性误导，将尾结点next与头结点next混为一谈。D项看似复杂，实则紧扣"带头结点"这一结构特征，是区分"有无头结点"判空逻辑的关键点。

若去掉"带头结点"条件，空链表判空需head == NULL；若改为循环双链表，空链表则需head->next == head && head->prev == head。命题人想考的是：链表类型（循环/非循环）、是否有头结点、指针语义（NULL/自指）这三个维度如何组合决定判空逻辑。刷到类似题先问"有无头结点？是否循环？"，即可快速锁定判空条件。