2.3 选择题讲评：把“已知什么指针”写在草稿第一行

链表选择题的复杂度取决于题目交给你的信息。先写：有头指针、尾指针、目标结点，还是目标前驱？再判断是否需要遍历。

单选 1：带头结点单链表为空的条件是 A head==NULL；B head->next==NULL；C head->next==head；D head->data==0。普通非循环单链表选 B；C 是常见循环带头链的空表条件。

多选：已知非空单链表中结点 p，哪些可在 $O(1)$ 完成？A 在 p 后插入；B 删除 p 的后继；C 求 p 的前驱；D 求表长。答案 A、B。单链表没有反向链接，C 通常从头找；D 若结构没有维护长度也要遍历。

指针推演题：在 p 后插入 s，若执行 p->next=s; s->next=p->next;，结果 s->next==s，形成自环并丢失原后继。正确顺序是先 s->next=p->next，再 p->next=s。

循环链表题：若只设尾指针 rear，首结点可由 rear->next 常数时间得到；若带头结点，则要根据约定判断 rear->next 是头结点还是首数据结点。题目未给约定时不可擅自套结论。

双链表题：删除 q 后必须同时保证 q->prev->next=q->next 与 q->next->prev=q->prev，边界处或用哨兵，或判空。只改一个方向，正向遍历可能正常，反向遍历却会访问悬空结点。

错解反馈：见到“链表”就选 $O(1)$，忽略定位条件；把头结点算入表长；用静态链表的数组下标相邻性代表逻辑相邻，都是典型概念偷换。

迁移题（多选）：仅给循环单链表尾指针，哪些通常可 $O(1)$？A 访问首结点；B 尾插；C 求第 $i$ 个元素；D 查找给定值。答案 A、B。验收要求为每项写出需要经过的指针边数。