专题 16 链表 · 复习强化

考点：节点两域结构（A1）。

（A1）考点：节点两域结构——链表节点由数据域与指针域组成，指针域存下一节点地址。

解析：本题考查节点两域结构。数据域装内容，指针域负责把散落的节点串成逻辑顺序，struct Node { int data; Node* next; }; 是标准形态。指针域是链表区别于数组一切特性的根源。

排除法：D 选下标与长度的人把数组的配套概念搬进了节点；C 选键与值的人描述的是映射结构；B 选地址与编号的人把「节点自身的地址」与「自身内容」混为一谈。

考点：头指针与首节点（A2）。

（A2）考点：头指针与首节点——head 存首节点地址，为 NULL 即空表。

解析：本题考查头指针与首节点。head 是进入链表唯一的入口：它指着谁，谁就是第一个节点；它谁都不指（NULL），链表就是空的。头插删头等操作都会改动 head 的指向。

排除法：A 以为 head 本身是节点的人没分清「指针」与「被指者」，head 没有 data 域；D 以为 head 存长度的人把它当成了长度计数器；C 以为头指针永不能变的人忘了头插法的本质就是改 head。

考点：物理存储不连续（A3）。

（A3）考点：物理存储不连续——节点按需分散在内存各处，靠指针连成逻辑链。

解析：本题考查物理存储不连续。每个 new Node 申请到哪里全凭分配器安排，两个逻辑上相邻的节点物理上可能相距很远；「下一个在哪」的信息完全由指针域携带，与内存位置无关。

排除法：C 选连续内存的人把数组的存储形态错安给链表；D 选按地址从大到小的人虚构了不存在的排列规则；B 选同一字节的人违反了基本物理常识。

考点：长度动态变化（A4）。

（A4）考点：长度动态变化——链表按需增删节点，不预估容量、不搬移其他元素。

解析：本题考查长度动态变化。要存就 new 一个挂上去，不要就摘下来 delete，链表长度随时伸缩；数组则要在定义时定长，装满后想扩容得整体搬家。动态性是链表的核心卖点。

排除法：B 选长度固定的人把数组的限制错记成链表的；A 选最多一百个的人把教学示例的规模当成了上限；D 选自动翻倍的人把 vector 的扩容策略错安在裸链表上。

考点：尾节点空标记（A5）。

（A5）考点：尾节点空标记——尾节点的 next 存 NULL，表示链到此为止。

解析：本题考查尾节点空标记。NULL 是「没有下一个」的公认记号，一切遍历循环都以 p != NULL 收尾。它不占额外空间、判断零成本，是链表收尾的标准设计。

排除法：A 选存自身地址的人描述的是循环链表的单节点特例，不是常规单链表；B 选存头节点地址的人描述的是循环链表；D 选存数值 $-1$ 的人把「下标记号」的用法错安到指针域上——指针域只能放地址或空。

考点：空链表（A6）。

（A6）考点：空链表——头指针为 NULL 即链表无任何节点。

解析：本题考查空链表。链表没有独立的长度字段，空与不空只看 head：head == NULL 空表，反之非空。所有链表操作动第一步都该先过这道判空闸。

排除法：C 选 $0$ 号下标的人把数组空判（下标越界）搬了过来；D 选数据域为 $0$ 的人混淆了「节点存在但值为 0」与「没有节点」；A 选长度变量为 $1$ 的人凭空造出了一个不存在的字段。

考点：三种链表形态总览（A7）。

（A7）考点：三种链表形态——单向、双向、循环是链表的三种基本形态。

解析：本题考查三种链表形态。单向每节点一根向后的指针；双向再加一根向前的；循环把尾接回头形成圈。三者可以组合（如双向循环链表），本卷 D、E 组分别展开后两种。

排除法：A 选顺序、索引、散列的人把存储结构的分类学（索引结构、散列结构）错当链表形态；D 选大中小的人按规模分类驴唇不对马嘴；C 选静态、动态、虚的人混入了不规范的叫法——静态链表只是实现方式，虚链表不存在。

考点：链表与数组对比（A8）。

（A8）考点：链表与数组对比——数组连续内存下标直达，链表指针串联顺藤摸瓜。

解析：本题考查链表与数组对比。一句话定位：数组「找得快、插删慢」，链表「插删快、找得慢」。根源就在存储方式：连续带来 $O(1)$ 定位也带来 $O(n)$ 搬移，分散带来自由增删也带来只能顺序走。

排除法：B 选只能存整数的人给数组加了不存在的限制；D 选链表永远省内存的人忘了每个节点要多付一个指针域的开销；A 选数组元素不能改的人把「定长」误解成了「只读」。

考点：遍历（B1）。

（B1）考点：遍历——从 head 出发沿 next 逐节点走到 NULL。

解析：本题考查遍历。链表遍历的固定节奏：for (Node* p = head; p != NULL; p = p->next)。方向唯一（向后）、步长唯一（一步），任何「跳着走」「回头走」的想象都不成立。

排除法：C 选按下标跳转的人忘了链表没有下标随机访问；B 选先跳尾部往回走的人把双向/循环链表的特例当成通则；A 选任选节点向两边扩展的人描述的是双向链表且起点任意，单链表做不到。

考点：查找（B2）。

（B2）考点：查找——单链表查找只能从首节点逐个比较。

解析：本题考查查找。链表无序无下标，二分的「看中间」都做不到——连中间都定位不了；唯一手段就是从头顺着比。这是 A5 组「链表找得慢」的具体来源。

排除法：B 选用二分法的人忘了二分需要随机访问中点，链表不具备；D 选直接算下标的人把数组的定位方式错安过来；C 选先排序再找的人本末倒置——排序本身就要先遍历，代价远超一次顺序查找。

考点：头插法（B3）。

（B3）考点：头插法——先接后继再改头：t->next = head; head = t。

解析：本题考查头插法。两步顺序是铁律：先把新节点接到旧首节点前面，再让 head 认新节点。头插法每次 $O(1)$，代价是输入顺序与链上顺序恰好相反（B8）。

排除法：D 选先改 head 再接后继的人会把旧链整个丢掉——t->next = head 此时接的是 t 自己；A 选 t->next = NULL 的人把新节点接到了虚空；C 选只改 head->next 的人把新节点插到了第二个位置而非头部。

考点：尾插法（B4）。

（B4）考点：尾插法——知道尾指针即可一步接尾，否则要从头走到尾。

解析：本题考查尾插法。尾部插入的钥匙是「找到尾」：维护尾指针 tail 时 tail->next = t 即成；没有尾指针就得从头走 $O(n)$。I2 是带尾指针的标准建链代码。

排除法：C 选把新节点指头的人描述的是循环链表尾插的一半；B 选直接 head = t 的人做成了头插且丢了旧链；D 选不需要尾部信息的人低估了「找尾」的成本。

考点：指定位置插入（B5）。

（B5）考点：指定位置插入——先接新节点的后继，再让前驱指向新节点。

解析：本题考查指定位置插入。t->next = p->next; p->next = t; 顺序不能反：第一句把后继先存进新节点，第二句才安全地让前驱改口。反过来的灾难见 P1。四行代码两步走，是链表最核心的手工操作。

排除法：C 选先改前驱的人会让 t->next = p->next 拿到 t 自己，原后继失联；B、A 选只改一处的人都会造成断链或丢节点——两处各管一根指针，缺一不可。

考点：删除节点（B6）。

（B6）考点：删除节点——前驱跨接后继，再释放被删节点。

解析：本题考查删除节点。p->next = q->next; 让 p 直接指到 q 的后面，q 从链上摘除，最后 delete q 归还内存。跨接在前、释放在后，顺序颠倒就成了释放后使用（P4）。

排除法：C 选直接释放的人让链在 q 处断裂，后面整段丢失；A 选 q->next = p->next 的人把赋值方向写反，链结构完全错乱；D 选清零数据域的人只抹了内容，节点还挂在链上占着位置。

考点：访问第 k 个（B7）。

（B7）考点：访问第 k 个——链表定位第 k 个节点要逐步走，O(k)。

解析：本题考查访问第 k 个。链表没有下标直达能力，想到达第 $k$ 个节点只能从第一个走 $k-1$ 步；这也是链表 «数组 在随机访问上的差距来源。数组同样的访问是 $O(1)$。

排除法：C 选一步直达的人把数组的下标访问错安过来；A 选 $\log_2 k$ 的人给它安上了二分的复杂度；B 选与 $k$ 无关常数的人同样没抓住「顺藤摸瓜」的本质。

考点：头插尾插输出顺序（B8）。

（B8）考点：头插尾插输出顺序——头插逆序、尾插正序。

解析：本题考查头插尾插输出顺序。头插把每个新元素放到最前面，先来的被压到后面，输出倒序 4 3 2 1；尾插按序接尾，输出正序 1 2 3 4。想要「按读入顺序输出」选尾插，想要「逆序」头插白送。

排除法：A 两组答案选反的人把两种插法的作用记反；B 选两组都正序的人没见过头插的倒序效果；D 选两组都倒序的人同样混淆——尾插恰恰保持原序。

考点：链表插入删除复杂度（C1）。

（C1）考点：链表插入删除复杂度——定位后插删本身只改指针，O(1)。

解析：本题考查链表插入删除复杂度。前提「已定位」很关键：位置拿到了，插入删除就是改两根指针的活，与链表多长无关。若把「从头找位置」算上则整体是 $O(n)$——快的只是插删动作本身。

排除法：B 答 $O(n)$ 搬移的人把数组的代价错安过来，链表不动任何其他节点；C 答 $\log_2 n$ 的人给它安上了二分的量级；A 答 $O(n^2)$ 的人凭空夸大了两个数量级。

考点：数组插入删除复杂度（C2）。

（C2）考点：数组插入删除复杂度——中部插删平均搬移约一半元素，O(n)。

解析：本题考查数组插入删除复杂度。中部插入要把后半段整体后挪一格，删除要前挪补洞，平均搬移 $n/2$ 个元素，量级 $O(n)$。这是链表在密集插删场景的核心优势来源。

排除法：C 答只需 $1$ 次操作的人只看到了「覆盖一个格子」，忘了后面整排要挪；D 答 $\log_2 n$ 的人把插删与二分查找的量级混淆；A 答直接覆盖的人描述的是「替换值」，不是插入删除。

考点：链表查找复杂度（C3）。

（C3）考点：链表查找复杂度——链表查找只能顺序扫描，O(n)。

解析：本题考查链表查找复杂度。链表不支持随机访问，看不了中间，跳不了步，查找只能从头一个个比，最坏 $n$ 次。链表「插删快、查找慢」的账要两头算。

排除法：C 答 $O(1)$ 的人以为有直达手段；D 答 $\log_2 n$ 的人忘了二分的前提（有序+随机访问）链表一条都不占；B 答 $O(n\log_2 n)$ 的人把排序的量级错安在查找上。

考点：头尾操作对比（C4）。

（C4）考点：头尾操作对比——单链表头插 O(1)，尾插无尾指针则 O(n)。

解析：本题考查头尾操作对比。头部永远是 head 现成指着，插入删除都是 $O(1)$；尾部若不维护尾指针，每次都要从头走到底。所以「频繁尾插」要么带尾指针，要么改用循环链表带尾指针（E4）。

排除法：A 答两者都 $O(1)$ 的人默认了尾指针的存在，普通单链表没有；B 答头 $O(n)$ 尾 $O(1)$ 的人把方向整个弄反；C 答两者都 $O(n)$ 的人低估了头部操作的便捷。

考点：中部插入对比（C5）。

（C5）考点：中部插入对比——链表改指针即插，数组要搬后半段。

解析：本题考查中部插入对比。同样「在第 100 个元素后插一个」：链表定位后改两根指针完事；数组要把后面全部元素逐个后挪。插删密集的场合链表显著占优（前提是位置信息已掌握或顺序维护）。

排除法：C 选数组占优的人把「下标直达」的好处错用在插删场景——直达帮不了搬移；A 选代价完全相同的人没做过两边的操作数对比；B 选两者都不适合的人下了过重的结论，链表正是为此而生。

考点：内存连续性（C6）。

（C6）考点：内存连续性——数组连续一整块，链表分散且每节点多付一个指针域。

解析：本题考查内存连续性。数组要一次申请到位才能保证连续；链表节点零散分配、按需领取，代价是每个节点多存指针（双向还要两根）。内存形态差异是两者一切行为差异的根源。

排除法：A 选都连续的人没理解链表的分配方式；D 选链表更省内存的人忘了指针域开销——小数据场景链表反而更费；C 选数组元素靠指针连接的人把链表的连接方式错安给数组。

考点：三域节点（D1）。

（D1）考点：三域节点——双向链表节点含数据、前驱指针、后继指针。

解析：本题考查三域节点。struct DN { int d; DN* prev, *next; }; 比单链表多出的 prev 是「往回走」的全部资本，双向链表的能力全部由此生长。

排除法：B 选下标与长度的人还是数组的配套概念；A 选两个数据域的人把 prev 的用途完全理解错；D 选头尾指针的人把整表级别的指针错安进了单个节点。

考点：前驱后继（D2）。

（D2）考点：前驱后继——p->prev 与 p->next 分别访问前驱与后继。

解析：本题考查前驱后继。命名上 prev/next 是通用习惯（也有用 l/r 或 front/back 的，读代码认语义即可）；有了前驱指针，「找上一个」从 $O(n)$ 降为 $O(1)$。

排除法：B 选 left/right 的人把特定代码库的命名当成了唯一标准；A 选 p-1/p+1 的人把指针运算错用在链表上——相邻节点地址不连续；C 选函数形式的人把成员访问语法记错。

考点：双向插入（D3）。

（D3）考点：双向插入——p 与 q 之间插入 t 要改 4 根指针。

解析：本题考查双向插入。四方各改一根：t->prev = p; t->next = q; p->next = t; q->prev = t;。漏任何一根都会造成方向不一致（P6）。对比单链表的 2 根，这就是双向的代价。

排除法：C 答 $2$ 根的人只改了 t 自己，p 与 q 还互相指着，t 被晾在链外；B 答 $1$ 根的人漏得更多；A 答 $6$ 根的人多算了两根不存在的指针。

考点：双向删除（D4）。

（D4）考点：双向删除——前后邻居互指，再释放自己。

解析：本题考查双向删除。p->prev->next = p->next; p->next->prev = p->prev; 两句让前驱与后继直接牵手，p 从两个方向的链上同时消失，最后释放。这是双向链表最舒展的操作——单链表删节点还得先找前驱。

排除法：A 选只释放 p 的人让链在 p 处两个方向同时断裂；B 选只改一处的人造成单向断链；D 选 p->next = p->prev 的人把「让邻居互指」写成了「自己乱指」。

考点：逆序遍历（D5）。

（D5）考点：逆序遍历——双向链表沿 prev 回走，单链表做不到。

解析：本题考查逆序遍历。从 tail 出发 p = p->prev 一步步回到头，与正向遍历一样自然。单链表的指针只有向后的单行道，想倒着走只能把整条链先逆置（J4）或借助数组缓存。

排除法：C 选两者同样方便的人忘了单链表指针的单向性；A 选单链表更快的人方向都没弄清；B 选双向无法反向的人正好说反——反向恰是双向存在的意义。

考点：双向优势与代价（D6）。

（D6）考点：双向优势与代价——多一个指针换「任意节点直接找前驱」。

解析：本题考查双向优势与代价。有了 prev，删除给定节点不必先从头找前驱，反向遍历随取随用；代价是每个节点多 8 字节指针与插入删除时多改两根指针。要不要双向，看「找前驱」的频率高不高。

排除法：C 选查找 $O(1)$ 的人高估了双向的能力——找值仍要扫；B 选内存更少的人正好说反；D 选长度翻倍的人把不相干的性质扯了进来。

考点：哑节点与哨兵（D7）。

（D7）考点：哑节点与哨兵——附加一个不存数据的节点，统一头部特判。

解析：本题考查哑节点与哨兵。链表最烦的边界是「删的恰好是头节点」「插到最前面」——此时 head 本身要变。加一个永远在首位的哑节点后，真实节点统统「有前驱」，删除插入统一按普通节点处理。它自己不参与数据。

排除法：D 选提速查找的人把边界简化误当性能优化；B 选存放数据的人没抓住「哑」字——它不装数据；A 选标记损坏的人把它当成了故障标志，恰恰相反，它是让代码更稳的构件。

考点：定义尾指头（E1）。

（E1）考点：定义尾指头——循环链表尾节点的 next 指回头节点。

解析：本题考查定义尾指头。把单链表的 NULL 换成 head，链就闭合成圈：从任何点出发都能走遍全圈。它没有天然的「终点标记」，遍历终止的判定方式随之改变（E2）。

排除法：C 选每节点两根指针的人描述的是双向链表；B 选尾存 $-1$ 的人还是单链表的思维；D 选头有 prev 的人描述的是双向循环链表的一半特征。

考点：遍历终止判断（E2）。

（E2）考点：遍历终止判断——循环链表以「回到起点」为终止。

解析：本题考查遍历终止判断。标准写法 p = head; do { 访问 p; p = p->next; } while (p != head);——先走再判，保证起点也被访问且恰好一圈。若先判后走用 while (p != head) 起步条件即为假，一个都访问不到。

排除法：D 选判 NULL 的人会把 E6 的死循环引来；C 选判 p->next == p 的人只适用于单节点自环的特例；B 选数满 $100$ 步的人把教学示例的规模当成了循环条件。

考点：约瑟夫环（E3）。

（E3）考点：约瑟夫环——循环链表天然模拟围圈报数出列。

解析：本题考查约瑟夫环。人围成圈 = 循环链表；报数 = 指针沿 next 移动；出列 = 删节点。圈的形态在删除过程中始终保留，模拟直白。K6 与 O4 分别考出列顺序与幸存者。数组也能做（模下标），但每次删除要搬移。

排除法：A 选普通数组的人也能做但删除的搬移代价与「圈」的直观性都吃亏，题干问的是「最适合自然模拟」；D 选栈的人方向反了；B 选二叉树的人引入了完全无关的结构。

考点：带尾指针循环链表（E4）。

（E4）考点：带尾指针循环链表——凭 tail 一步拿到尾与头，头尾操作全 O(1)。

解析：本题考查带尾指针循环链表。循环结构里 tail->next 就是头节点：尾插先接 t（t->next = tail->next; tail->next = t; tail = t;），头插经由 tail->next 改头。两个方向的 $O(1)$ 操作使它成为「既要头又要尾」场景的利器。

排除法：C 选查找任意值的人高估了它的能力——查找照样要扫圈；A 选访问正中间的人忘了定位中点仍要逐个走；D 选排序的人把组织结构的便利错当排序能力。

考点：任一节点遍历全表（E5）。

（E5）考点：任一节点遍历全表——循环链表从任何节点出发都能走完全圈。

解析：本题考查任一节点遍历全表。圈没有断点，入口选谁都行：从任意节点出发沿 next 走，回到出发点时全表已扫一遍。单链表从中途某节点出发，只能访问「它及其后继」，前面的够不着。

排除法：A 选一步跳转的人把遍历能力误当随机访问；C 选不需要指针的人忘了圈就是靠指针闭合的；B 选自动有序的人把结构与有序性混为一谈。

考点：循环条件死循环（E6）。

（E6）考点：循环条件死循环——循环链表没有 NULL，判 NULL 永远为真。

解析：本题考查循环条件死循环。单链表的终止条件建立在「尾指 NULL」上；循环链表把这个标记取消了，p != NULL 成了永真式，循环停不下来。正确终止见 E2 的「回到起点」。

排除法：D 选恰好正确的人忽略了程序根本停不下来；A 选编译报错的人把运行期逻辑错误当成编译期检查；C 选自动断开的人给链表虚构了自我修复能力。

考点：链表实现栈（F1）。

（F1）考点：链表实现栈——头部即栈顶，头插为入栈、删头为出栈。

解析：本题考查链表实现栈。栈只在一端进出，选头部最划算：入栈就是头插（$O(1)$），出栈就是删头节点（$O(1)$），head 天然扮演栈顶指针。若选尾部，删尾要先找前驱，单链表做不到 $O(1)$。

排除法：D 选尾部的人没算删尾的账——单链表删尾要走到倒数第二个；A 选正中间的人把栈的两端性质完全丢弃；B 选哪端都一样的人没比较过两端操作的代价。

考点：链表实现队列（F2）。

（F2）考点：链表实现队列——头指针管出队、尾指针管入队，两端都 O(1)。

解析：本题考查链表实现队列。队列先进先出：从尾入（tail->next = t）、从头出（删头更新 head），配齐两个指针即可全 $O(1)$。O1 是这套配置的操作执行题。只留一个指针必有一端退化成 $O(n)$。

排除法：D 选只留头指针的人每次入队要走全链；C 选只留尾指针的人每次出队要走全链；A 选不能用链表的人过度设限——链表恰是队列的经典实现之一。

考点：链地址法挂链（F3）。

（F3）考点：链地址法挂链——桶内冲突元素用链表组织，按需增长插删灵活。

解析：本题考查链地址法挂链。哈希桶里会撞进来几个元素事先不定，链表「长度随便长、插入只挂指针」的性质正合需求。此处在纲外仅作链表应用了解，哈希表的系统知识属提高级。

排除法：D 选让哈希函数更快的人把存储结构与函数计算混为一谈；A 选防止冲突的人夸大了它——冲突照样发生，只是被有序收纳；B 选让桶有序的人没注意链地址法的链表通常按插入顺序挂，无序。

考点：数据量未知选链表（F4）。

（F4）考点：数据量未知选链表——按需逐个申请，不预估容量不整体搬迁。

解析：本题考查数据量未知选链表。定长数组赌小了装不下、赌大了浪费；链表来一个节点申请一个，规模弹性极大。代价是查找定位慢——选型时配合访问模式一起权衡。

排除法：D 选查找更快的人正好把短板说成长处；A 选支持随机访问的人与事实相反；C 选不需要内存的人说了句不可能的话——每个节点都要实打实的内存。

考点：有序链表插入维护（F5）。

（F5）考点：有序链表插入维护——每次定位到第一个更大者前插入，链始终有序。

解析：本题考查有序链表插入维护。插入时从头找「第一个比新值大的节点」，插到它前面（J8、O3 的代码形态）；链长 $n$ 时每次插入定位 $O(n)$，但序列随时整体有序可输出。对比数组版有序维护的搬移，链表版只改指针。

排除法：C 选不比较任何值的人没想过「插到哪」本身就需要比较；B 选自动排序的人把希望寄托给了不存在的魔法；D 选查找 $O(1)$ 的人把「随时有序」误当「随时直达」。

考点：快慢判环（G1）。

（G1）考点：快慢判环——慢一步快两步，有环必相遇，无环快指针到 NULL。

解析：本题考查快慢判环。无环时快指针一路领先先撞 NULL；有环时两者进入圈内，每轮快指针比慢指针多走一步、距离逐步缩短，必在某点重合。K3、M1 是执行追踪。这是笔试面试双高频的经典。

排除法：B 选快指针先走完的人没想过有环时根本没有「完」；A 选同速的人让两指针永远保持初始距离，遇不上；D 选必须三步的人把步长与相遇的关系理解错——两步恰好保证每轮追近一步，三步可能跨越错过（存在不相遇的环长组合）。

考点：快慢找中间（G2）。

（G2）考点：快慢找中间——快两步慢一步，快到尾时慢在中点。

解析：本题考查快慢找中间。快指针速度是慢的两倍，快走完全程时慢恰好走了一半。奇数长度停在正中，偶数长度停在后半第一个（M2 实测 $6$ 节点停 $4$）。一次遍历拿到中点，不用先数长度再走一遍。

排除法：B 选慢两步快一步的人把配比弄反，慢的反而快；D 选从两端相向而行的人把数组双指针的套路错安到只能单向走的链表上；A 选快指针先到中点等着的人没理解「等」本身就是另一种提前定位。

考点：倒数第 k（G3）。

（G3）考点：倒数第 k——快指针先行 k 步，两指针同速，快到 NULL 慢就位。

解析：本题考查倒数第 k。先让快指针领先 $k$ 步，随后同速前进，两指针间距恒为 $k$；快指针触到 NULL 时，慢指针离链尾恰好 $k$ 个位置——正是倒数第 $k$。一次遍历解决，M3 还把删除动作接了上去。

排除法：B 选慢指针先走的人把「领先」与「滞后」弄反，慢指针跑到了参照系外；D 选反向而行的人又用了双向链表才有的能力；C 选先数长度再走的人用了两次遍历，能做但不是双指针一次遍历的解法。

考点：双指针遍历（G4）。

（G4）考点：双指针遍历——前驱当前同速推进，删除时前驱现成。

解析：本题考查双指针遍历。p 与 q=p->next 同速前进，任何时刻 p 都是 q 的前驱；要删 q 时 p->next = q->next 直接动手，不必再从头找前驱。单指针删除都要付一次回头路，这就是双指针的收益。

排除法：C 选速度快一倍的人把「两个指针」误解成「速度翻倍」；D 选省一半内存的人凭空想象了不存在的节省；B 选跳过偶数节点的人把另一个技巧（按 step 跳）错安在本技巧上。

考点：快指针步长条件（G5）。

（G5）考点：快指针步长条件——fast 与 fast->next 两个条件各防一种踩空。

解析：本题考查快指针步长条件。走两步是两次「取 next」：fast 本身可能是 NULL（第一步就踩空），fast->next 可能是 NULL（第二步踩空），两个条件分别守住两步。缺第二个条件在奇数长度链上必崩（M5 展开）。

排除法：A 选两条件重复的人没推过奇数链的收尾；B 选第一个条件加速的人给条件安了不相干的职能；C 选让慢指针变快的人把条件的保护对象弄错——它保护的是快指针自己。

考点：静态结构与 next 数组（H1）。

（H1）考点：静态结构与 next 数组——nxt[i] 存后继下标，-1 为链尾。

解析：本题考查静态结构与 next 数组。把「指针」换成「下标」：data[i] 是内容，nxt[i] 是下一节点的数组下标，$-1$ 表示到头。逻辑与动态链表完全同构，物理上却是纯数组，不需要 new/delete。

排除法：B 选存数据值的人把两个数组的分工弄混；C 选存总长度的人把全局信息塞进了每格；A 选存真实地址的人没理解「模拟」的本质——用下标顶替地址。

考点：头指针是下标（H2）。

（H2）考点：头指针是下标——静态链表的 head 是存首节点下标的整型变量。

解析：本题考查头指针是下标。动态链表的入口是 Node*，静态链表把入口降格为 int head——存的是首节点的下标号。空表用 $-1$ 表示（与链尾标记一致）。概念换壳，思想不变。

排除法：C 选 Node* 指针的人没换掉动态思维；D 选数组长度的人把入口与规模混淆；B 选固定 $0$ 的人忘了首节点未必放下标 $0$——数组哪个位置空闲就用哪个（L 组的链首元素就在下标 $0$ 只是数据安排的巧合）。

考点：静态插入（H3）。

（H3）考点：静态插入——先接后继下标再改前驱，与动态版同构。

解析：本题考查静态插入。nxt[j] = nxt[i]; nxt[i] = j; 与动态链表「先接后继再改前驱」一字不差地对应，只是指针换成下标赋值。顺序同样不能反，反了同样丢后继。

排除法：D 选先改前驱的人让 nxt[j] = nxt[i] 拿到 $j$ 自己，原后继失联；C 选只改一句的人要么断链要么没真正挂上；A 选交换 data 的人把插入做成了换值。

考点：静态删除（H4）。

（H4）考点：静态删除——nxt[i] = nxt[j] 跨过 j 即逻辑删除。

解析：本题考查静态删除。让前驱直接指向被删者的后继，$j$ 从链上消失。注意静态链表常常不真清空格子——把 $j$ 号位挂回空闲链即可复用；是否回收是工程选择，逻辑删除一步到位。

排除法：D 选搬移所有元素的人把数组的删除代价错安过来；A 选清零 data 的人节点还挂在链上会被遍历到；C 选清零 nxt 的人把 j 的后继信息毁了但 j 可能还在链上。

考点：容量受限（H5）。

（H5）考点：容量受限——静态链表节点数不能超过数组容量。

解析：本题考查容量受限。数组开多大，节点上限就是多大，超了就无处安放；动态链表按需申请理论上只受系统内存限制。开数组前估算规模（或开足够大的安全值）是静态链表的使用纪律。

排除法：D 选不能插删的人与事实相反——改下标即可；C 选只能存字符的人把元素类型与存储方式混淆；B 选查找从尾部开始的人虚构了不存在的规则——查找永远从头下标出发。

考点：头插建链（I1）。

（I1）考点：头插建链——依次头插 1 到 4，链上顺序倒置为 4 3 2 1。

解析：本题考查头插建链。每来一个新数都插到最前：$1$ 进链为 1；$2$ 头插变 2 1；$3$ 变 3 2 1；$4$ 变 4 3 2 1。头插两步 t->next = head; head = t; 逐轮执行，输出自然逆序。

排除法：A 答 1 2 3 4 的人按尾插的结果理解了头插；C、B 答 1 4 2 3 与 4 1 3 2 的人对两步接链的次序理解错乱，头插的次序是确定性的不会随机。

考点：尾插建链（I2）。

（I2）考点：尾插建链——带尾指针依次接尾，保持原序 1 2 3。

解析：本题考查尾插建链。tail 始终指最后节点：空表时新节点既是头也是尾；其后每次 tail->next = t 接上再挪 tail。链上顺序与输入一致，输出 1 2 3。

排除法：A 答 3 2 1 的人把头插的倒序效果错安过来；C、B 答 1 3 2 与 2 3 1 的人对空表分支（首节点要单独认头）理解有洞，尾插法一旦首节点接错位就全乱。

考点：遍历求和（I3）。

（I3）考点：遍历求和——沿 next 累加 data，4+6+2=12。

解析：本题考查遍历求和。循环从 head 走到 NULL，把每个节点的 data 加进 s：$4+6+2=12$。链表求和与数组求和同构，只是「下一元素」从下标自增换成 p = p->next。

排除法：A 答 $4$ 的人只算了首节点，以为循环不推进；D 答 $6$ 的人只算了中间节点；B 答 $3$ 的人数的是节点个数不是和。

考点：统计节点数（I4）。

（I4）考点：统计节点数——遍历计数，五节点得 5。

解析：本题考查统计节点数。链表没有现成的长度字段，长度只能现走现数：每过一个节点 n++，五节点输出 $5$。这也是快慢指针找中点前「先数长度」做法的基础步骤。

排除法：C 答 $4$ 的人差一，多半把循环条件写成了 p->next != NULL 提前一步停（P3）；A 答 $15$ 的人把求和的结果与计数混淆；D 答 $1$ 的人以为只统计首节点。

考点：找最大值（I5）。

（I5）考点：找最大值——打擂台沿链比大小，9 胜出。

解析：本题考查找最大值。擂主初值取首节点 $3$，随后 $9$ 攻擂成功、$5$、$7$ 挑战失败，输出 $9$。链表版打擂台与数组版逻辑相同，注意擂主初值不能凭空设 $0$（负数链会错），取首节点最稳。

排除法：A 答 $3$ 的人以为初值即终值；C 答 $7$ 的人把最后看到的较大值当成了最大值；D 答 $24$ 的人把求和的结果错当最大值。

考点：条件统计（I6）。

（I6）考点：条件统计——遍历中按条件计数，大于 5 的有 2 个。

解析：本题考查条件统计。链上数据 $2,5,3,8,6$，大于 $5$ 的只有 $8$ 与 $6$，输出 $2$。注意 $5$ 本身不大于 $5$，等于不算。

排除法：A 答 $5$ 的人把链长当成了满足条件的个数；B 答 $3$ 的人把等于 $5$ 的也算进去；C 答 $14$ 的人算的是满足条件元素之和而非个数。

考点：清空释放（I7）。

（I7）考点：清空释放——先存后继再删当前，输出 1 2 3 且无泄漏。

解析：本题考查清空释放。循环体三步：记下 t、head 前移、delete t。每删一个先输出其值，依次 1 2 3。关键在于先取后继再删——删完再取就是释放后使用（P4）。

排除法：B 答 3 2 1 的人以为删除从尾部开始，释放永远从头走；C 答 1 的人以为只删首节点；D 答无输出的人没看到循环里的 cout。

考点：判空处理（I8）。

（I8）考点：判空处理——空表输出 empty，避免解引用 NULL。

解析：本题考查判空处理。head == NULL 分支先接住空表情形，输出 empty；若不判空直接 head->data，就是对空指针解引用、当场崩溃（P5）。判空是链表代码的第一道防线。

排除法：B 答 $0$ 的人以为空表的数据域默认为零——节点都不存在，何谈数据域；D 答崩溃的人没看到 if 已把空表接住；A 答编译错误的人把运行期问题当成了编译期检查。

考点：指定位置插入（J1）。

（J1）考点：指定位置插入——先接 t 的后继再改 p 的指向，得 1 3 4 5。

解析：本题考查指定位置插入。p 指向 $3$：t->next = p->next 让 $4$ 先抓住 $5$，p->next = t 让 $3$ 改口认 $4$，链变 1 3 4 5。两步顺序（B5）是全程要点。

排除法：A 答 1 4 3 5 的人把新节点插到了 $3$ 之前——那是另一种操作（改前驱指向），本题代码插在后；B 答 1 3 5 4 的人把接尾误当成追加；C 答 4 1 3 5 的人以为改了 head。

考点：删除给定值（J2）。

（J2）考点：删除给定值——找前驱跨接删后继，删第一个 2 得 1 3 2。

解析：本题考查删除给定值。删除要改前驱的 next，所以循环找的是「值为 2 的节点的前驱」：p 停在 $1$（其后继是第一个 $2$），跨接后链变 1 3 2——只删第一个匹配，第二个 $2$ 安然无恙。

排除法：C 答 1 3 的人删了两个 $2$，但循环在第一次删除后就退出；D 答 1 2 3 的人以为删的是末尾的 $2$；A 答 2 3 2 的人以为删了头节点。

考点：头插执行追踪（J3）。

（J3）考点：头插执行追踪——空链头插 10 再头插 20，得 20 10。

解析：本题考查头插执行追踪。第一步后链为 10；第二步 $20$ 插到 $10$ 前面，链为 20 10。头插的两步对空链同样适用（t->next = NULL 即 head 的当前值），无需特判——这正是头插法的优雅之处。

排除法：D 答 10 20 的人没注意第二次也是头插；B、C 答 10 10 与 20 20 的人以为某次插入覆盖了旧值——两个节点都真实存在。

考点：逆置链表（J4）。

（J4）考点：逆置链表——头摘法逐个前插，1 2 3 4 翻成 4 3 2 1。

解析：本题考查逆置链表。三步循环：摘下原链头（存后继）、把它头插到新链 rev、继续。原链 1 2 3 4 逐个搬到 rev：1 → 2 1 → 3 2 1 → 4 3 2 1。$O(n)$ 一步到位，不借助数组。

排除法：C 答 1 2 3 4 的人以为只是复制没翻转；D、A 答 1 4 3 2 与 2 3 4 1 的人对「摘头前插」的某一步执行顺序理解错，翻转是严格确定的全倒序。

考点：删除第 k 个（J5）。

（J5）考点：删除第 k 个——p 停在第 k-1 个跨接删除，得 5 8 1 6。

解析：本题考查删除第 k 个。删第 $2$ 个要前驱（第 $1$ 个，值 $5$）跨接：p->next 从 $3$ 改指 $8$，链变 5 8 1 6。若删的是第 $1$ 个（头），得改 head 本身——这正是哑节点要解决的特例（D7）。

排除法：A 答 3 8 1 6 的人删成了头节点；D 答 5 3 1 6 的人删的是第 $3$ 个；B 答 5 8 6 的人多删了一个。

考点：找第 k 个（J6）。

（J6）考点：找第 k 个——从头走 k-1 步，第 3 个值是 8。

解析：本题考查找第 k 个。p 从 head 起，循环 k-1 次每次 p = p->next，停在第 $3$ 个节点，值为 $8$。链 5 3 8 1 6 的第 $k$ 个与数组下标 $k-1$ 一一对应。

排除法：B 答 $5$ 的人以为不用走步停在第 $1$ 个；C 答 $3$ 的人少走一步停在第 $2$ 个；D 答 $1$ 的人多走一步停在第 $4$ 个。

考点：判断递增（J7）。

（J7）考点：判断递增——逐对相邻比较，全部严格递增输出 1。

解析：本题考查判断递增。循环条件 p->next != NULL 保证每一对相邻节点 $(p, p->next)$ 恰好比一次：$1<3$、$3<5$、$5<7$ 全过，inc 保持真输出 $1$。写成 >= 是刻意把相等也判为非严格递增。

排除法：D 答 $0$ 的人没逐对比较就臆断失败；A 答 $7$ 的人输出成了尾节点值；B 答编译错误的人不了解指针条件完全合法。

考点：有序插入（J8）。

（J8）考点：有序插入——找第一个不小于新值的前驱插入，1 3 7 插 5 得 1 3 5 7。

解析：本题考查有序插入。循环让 p 停在「next 值 ≥ 5」的第一个节点（$3$）上：3 的 next 是 $7$，$7$ 不小于 $5$，停；两步插入后链变 1 3 5 7。条件用 < 保证相等时插在前面。

排除法：C 答 1 3 7 5 的人以为直接接尾；B 答 5 1 3 7 的人以为头插；A 答 1 5 3 7 的人对定位条件理解错插进了已排序段中间的错误位置。

考点：双向反向输出（K1）。

（K1）考点：双向反向输出——从尾沿 prev 回走，输出 3 2 1。

解析：本题考查双向反向输出。tail 指 $3$，p = p->prev 依次走到 $2$、$1$，再往前 prev 为 NULL 停止。反向遍历与正向完全对称，这是 prev 指针的直接兑现（D5）。

排除法：B 答 1 2 3 的人沿 next 正向走了；D 答 3 的人以为走一步就停，忘了循环条件是 p != NULL；C 答死循环的人没注意反向走到头节点后 prev 为 NULL 会自然终止。

考点：循环走 n 步（K2）。

（K2）考点：循环走 n 步——5 节点循环链走 7 步，7 mod 5 = 2，落在值 3。

解析：本题考查循环走 n 步。循环链走一圈回原点，位置只看步数模链长：$7 \bmod 5 = 2$，从 $1$ 出发跨过 $2$、$3$ 两步到第三个节点值 $3$。链上「走 n 步」类问题的通用心算就是模一圈。

排除法：D 答 $7$ 的人以为节点值跟着步数涨，链上根本没有 $7$；A 答 $2$ 的人少算一步停在了值 $2$；B 答 $5$ 的人对模运算用错被除数。

考点：判环代码（K3）。

（K3）考点：判环代码——快慢指针在环内相遇，meet 为 4。

解析：本题考查判环代码。慢指针路线 $1,2,3,4,2,\cdots$，快指针路线 $1,3,2,4,3,\cdots$：第 $3$ 轮慢在 $4$、快也在 $4$，相遇记录 meet = 4。只要入环，两指针每轮净接近一步，相遇只是时间问题。

排除法：C 答 $-1$ 的人以为快指针能逃出圈——环里没有 NULL，逃不掉；A 答 $2$ 的人把入环点当成了相遇点，相遇点取决于起步位置与追及过程；B 答死循环的人没看到 if (slow == fast) break 恰好接住相遇。

考点：双向插入执行（K4）。

（K4）考点：双向插入执行——四根指针逐行赋值后 1 与 3 之间接入 2。

解析：本题考查双向插入执行。逐行读代码：b.prev = &a 与 b.next = &c 先把新节点 $b$ 的两根指向邻居；a.next = &b 与 c.prev = &b 再让邻居认回 $b$——四根各就各位后链为 $1\leftrightarrow2\leftrightarrow3$。从头沿 next 遍历输出 1 2 3；反向沿 prev 也能得到 3 2 1，两个方向互为镜像。

排除法：C 答 2 1 3 的人以为新节点排到了最前；B 答 1 3 2 的人只改了 $b$ 自己的两根、漏了 a.next 与 c.prev 的认回；D 答 1 3 的人以为插入没有生效——四根赋值已把 $b$ 嵌入链中。

考点：循环尾插（K5）。

（K5）考点：循环尾插——带尾指针循环链表建链代码读一圈输出。

解析：本题考查循环尾插。逐轮追踪：$i{=}1$ 时空表，head = t 且 t->next = head 成自环，tail = t；$i{=}2$ 时 t->next = head 接头、tail->next = t 接尾，尾指针前移；$i{=}3$ 同理——链成 $1\to2\to3\to1$ 的圈。do-while 从 head 起输出一圈恰为 1 2 3，回到起点即止。

排除法：A 答 3 2 1 的人把头插的倒序错安给尾插；B 答 1 2 3 1 的人多输出了一圈起点——do-while 的条件会在回到 head 时及时收住；C 答 2 3 1 的人起点选错，head 始终指 $1$。

考点：约瑟夫出列（K6）。

（K6）考点：约瑟夫出列——5 人报 3，出列顺序 3 1 5 2 4。

解析：本题考查约瑟夫出列。模拟：$1,2,3$ 报到 $3$ 出列（$3$）；$4,5,1$ 报到 $1$ 出列（$1$）；$2,4,5$ 报到 $5$ 出列（$5$）；$2,4$ 报到 $2$ 出列（$2$）；剩 $4$。圈上删除用循环链表最直观（E3），O4 追问幸存者。

排除法：C 答 $3,4,5,1,2$ 的人只报了一轮就连续出列，忘了每次报数重新从 $1$ 开始；D 答 $1,2,3,4,5$ 的人没做任何报数；A 答 $5,4,3,2,1$ 的人把顺序整个倒过来凑数。

考点：沿 next 输出（L1）。

（L1）考点：沿 next 输出——head=0 走 nxt 得 7 3 9 5 1。

解析：本题考查沿 next 输出。链路由 nxt 勾勒：$0\to2\to1\to4\to3\to-1$，对应 data 为 $7,3,9,5,1$。注意节点在数组里的物理顺序（下标 $0,1,2,3,4$）与链上顺序完全无关——静态链表考的就是这层「下标当指针」的翻译。

排除法：A 答 7 9 3 1 5 的人按数组物理顺序读，没跟 nxt 走；C 答 7 3 1 5 9 的人跟错一格；B 答 7 3 9 1 5 的人末尾两步走岔。

考点：静态求和（L2）。

（L2）考点：静态求和——沿链累加 7+3+9+5+1=25。

解析：本题考查静态求和。遍历路径与 L1 相同，累加各 data：$7+3+9+5+1=25$。静态链表的求和统计与动态版同构，for (int p = head; p != -1; p = nxt[p]) 是标准循环形态。

排除法：B 答 $22$ 的人漏加了链上某个节点；A 答 $5$ 的人输出成了节点个数；C 答 $19$ 的人按数组物理顺序前四个数求和没走完整条链。

考点：静态插入（L3）。

（L3）考点：静态插入——下标 5 接进 9 之后，得 7 3 9 6 5 1。

解析：本题考查静态插入。nxt[5] = nxt[1] 让新节点先抓住原后继（下标 $4$），nxt[1] = 5 让 $9$ 改口认新节点；链变 $0\to2\to1\to5\to4\to3$，即 $7,3,9,6,5,1$。与动态插入同构，先接后改（H3）。

排除法：B 答 7 3 9 5 1 6 的人把新节点接到了链尾；C 答 7 3 6 9 5 1 的人把新节点插到了 $9$ 之前；D 答 6 7 3 9 5 1 的人以为插到了链首。

考点：静态删除（L4）。

（L4）考点：静态删除——nxt[1] = nxt[4] 跨过 5，得 7 3 9 1。

解析：本题考查静态删除。$9$（下标 $1$）的后继是下标 $4$（值 $5$）；执行 nxt[1] = nxt[4] 后 $9$ 直接指向下标 $3$（值 $1$），$5$ 被跨过，链变 $7,3,9,1$。被删格子的 data 还在数组里，但链上再也走不到它。

排除法：D 答 7 3 9 5 1 的人以为没改动；B 答 7 3 1 的人把 $9$ 也删了；A 答 9 5 1 的人把前半段丢了。

考点：静态查找（L5）。

（L5）考点：静态查找——沿 nxt 链查找值 5，落到下标 4。

解析：本题考查静态查找。沿链逐站核对 data[p]：$p{=}0$ 值 $7$、$p{=}2$ 值 $3$、$p{=}1$ 值 $9$、$p{=}4$ 值 $5$ 命中，pos 记为 $4$；随后 nxt[4]=3，$p{=}3$ 值 $1$ 不中，nxt[3]=-1 循环终止。静态链表的「地址」就是下标，查找返回的是下标而非指针。

排除法：B 答 $5$ 的人把查找值当成了答案下标。C 答 $3$ 的人跟链只走了三站漏了最后一跳。A 答下标 $1$ 的人以为按物理顺序找 $5$——物理位置与链上位置无关。

考点：静态建链（L6）。

（L6）考点：静态建链——尾插 10 20 30，nxt[1]=2、nxt[2]=-1。

解析：本题考查静态建链。按到达顺序分配下标：$10$ 得 $0$、$20$ 得 $1$、$30$ 得 $2$；尾插让前一个的 nxt 指向后一个，末节点 nxt 为 $-1$。所以 nxt[1] = 2（$20$ 的后继是 $30$）、nxt[2] = -1（$30$ 是尾）。

排除法：C 答 $-1$ 与 $2$ 的人把两格的值互换；D 答 $0$ 与 $1$ 的人没理解「指后继」写成自指；B 答 $1$ 与 $3$ 的人既自指又越界。

考点：判环执行（M1）。

（M1）考点：判环执行——快慢指针三追两赶在值 4 处相遇。

解析：本题考查判环执行。慢指针依次走到 $2,3,4$；快指针两步两跳依次到 $3,2,4$：第三轮两者同在节点 $4$，slow == fast 成立，输出 $4$。steps == 0 的附加条件只是为了让起点处 slow == fast 不被误判为「已相遇」。

排除法：B 答 $2$ 的人把入环点当成了相遇点；A 答 $1$ 的人以为起点即终点——起点同时出发但循环至少跑一轮；D 答 $3$ 的人追踪快指针路线时跳错一步。

考点：找中间执行（M2）。

（M2）考点：找中间执行——6 节点快慢指针停在后半第一个，值 4。

解析：本题考查找中间执行。慢：$1,2,3,4$；快：$1,3,5$ 后再跳将越过 NULL 触发条件停止——快指针停在 $6$ 处时（第三轮后 fast=6？逐轮核：初 $1,1$；一轮慢 $2$ 快 $3$；二轮慢 $3$ 快 $5$；三轮慢 $4$ 快 $6$；四轮条件 fast->next 为 NULL 不再进。慢停 $4$）。偶数长度取到后半第一个，是此写法的既定行为。

排除法：D 答 $3$ 的人以为偶数链取前中；A 答 $5$ 的人多数走了一步；C 答 $6$ 的人把快指针的终点当成了慢指针的落点。

考点：删倒数第 k（M3）。

（M3）考点：删倒数第 k——快指针先行 2 步，同速推进后慢指针停在待删前驱处。

解析：本题考查删倒数第 k。f 先行 $2$ 步到节点 $3$；随后 while (f->next) 推进直到 f 停在尾节点 $5$，此时 s 停在 $3$（倒数第 $3$ 个，即待删节点 $4$ 的前驱）；跨接删除后链变 1 2 3 5。用 f->next 而非 f 判停是为了让 s 恰好落在前驱上。

排除法：D 答 1 2 4 5 的人删的是倒数第 $3$ 个；A 答 2 3 4 5 的人删了头节点；C 答 1 2 3 4 5 的人以为没改动——跨接真实发生了。