第 7 章 链表 · 知识细节练习

考点：节点结构（A1）。

解析：链表节点 = 数据域（存值）+ 指针域（存下一个节点的地址）。C++ 中常用结构体定义：struct Node { int val; Node *next; };。✅ 正确

排除法：无（判断题）。混淆点：数组的"元素"没有指针域——链表靠指针域串联，这是与数组的本质区别（见 A3）。

关联 · 结构体（第 4 章 G1）：链表节点就是结构体 + 指针的组合；Node *next 是"指向下一个节点"的指针成员。

考点：头指针（A2）。

解析：链表用头指针（head）指向第一个节点；head == nullptr 表示空链表（一个节点都没有）。✅ 正确

排除法：无（判断题）。混淆点：头指针是指针变量（存地址），不是节点本身；链表操作几乎都要从 head 出发。

关联 · 空链表（A6）：空链表判断 = head == nullptr——几乎所有链表函数的第一件事。

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

解析：链表节点用 new 逐个动态创建，散落在内存各处，靠指针链接成逻辑序列——物理不连续、逻辑连续。✅ 正确

排除法：无（判断题）。混淆点：数组是物理连续（一块连续内存）；链表是逻辑连续（物理可分散）。

关联 · 内存连续（C7）：数组连续 → 按下标直接算地址（$O(1)$）；链表分散 → 只能顺着指针走（$O(n)$）——连续性是随机访问快慢的根源。

考点：长度动态（A4）。

解析：链表节点按需 new，随时可以加节点——不需要预先知道大小，天然动态。✅ 正确

排除法：无（判断题）。混淆点：数组大小在 C++ 中必须编译期确定（或 new[] 一次性分配）；链表没有这个限制。

关联 · 动态内存（G3）：new 分配、delete 释放——链表的增删与内存的分配释放一一对应。

考点：尾节点（A5）。

解析：单向链表最后一个节点的 next 为 nullptr——这是遍历终止的标志（见 B1）。✅ 正确

排除法：无（判断题）。混淆点：循环链表的尾节点指向头节点（见 E1）——"尾指针为空"是单链表的特征，别与循环链表混。

关联 · 遍历终止（B1）：while (p != nullptr) 正是利用尾节点的空指针停止。

考点：空链表（A6）。

解析：空链表 = 头指针为 nullptr（没有节点）。✅ 正确

排除法：无（判断题）。混淆点：头指针 ≠ 头节点——头指针是变量，头节点（哨兵，见 D7/G1）是真实存在的空壳节点，两者不同。

关联 · 头指针（A2）：if (head == nullptr) 是链表函数的"空表检查"，先判空再操作是安全第一原则。

考点：遍历链表（B1）。

解析：遍历 = 从 head 出发，沿 next 逐节点访问，直到 nullptr：for (Node *p = head; p; p = p->next)。✅ 正确

排除法：无（判断题）。混淆点：不能像数组那样 a[i] 跳跃——链表的访问路径是唯一的（单向的 next 链）。

关联 · 尾节点（A5）：p = p->next 前进，p == nullptr 停止——遍历终止条件就是尾节点的空指针。

考点：查找元素（B2）。

解析：单链表查找只能从头逐个比较，最坏要找遍全部 $n$ 个节点（目标在尾部或不存在）。✅ B

排除法：A $1$ 是最佳情况（在头部）；C $n-1$ 漏了"不存在也要查完 n 个"；D $\log n$ 是二分（链表不支持）。

关联 · 复杂度（C4）：链表查找 $O(n)$——"顺序访问"决定了它只适合小规模或已知位置的操作。

考点：头插法（B3）。

解析：头插 = 新节点 q 的 next 指向原头，再更新头指针：q->next = head; head = q;——新节点成为头。✅ 正确

排除法：无（判断题）。混淆点：头插不需要遍历（$O(1)$）；依次头插的结果是逆序（后插的在前，见 H2）。

关联 · 头插顺序（H2）：1,2,3 头插后是 3→2→1——头插常用于"反转录入顺序"。

考点：尾插法（B4）。

解析：单链表没有尾指针时，尾插要先遍历到最后一个节点再接新节点——$O(n)$。✅ 正确

排除法：无（判断题）。混淆点：维护一个 tail 指针（或循环链表带尾指针，见 E4）可把尾插降到 $O(1)$——"是否维护尾指针"决定尾插复杂度。

关联 · 头尾复杂度（C5）：头插 $O(1)$、尾插 $O(n)$（无尾指针）——建链时按需选头插或尾插。

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

解析：已知前驱 p、新节点 q：① q->next = p->next（新节点先连后继）② p->next = q（前驱再连新节点）——改 2 个指针。✅ B

排除法：A $1$ 个会断链；C $3$/$4$ 是双向链表的开销（见 D2）。

关联 · 指针顺序（G2/H4）：必须先 q->next = p->next 再 p->next = q——顺序反了会丢掉后面的链表（见 H4）。

考点：删除节点（B6）。

解析：删除节点 q（已知前驱 p）：p->next = q->next——前驱直接越过 q 指向后继，然后 delete q。✅ 正确

排除法：无（判断题）。混淆点：删除当前节点（不知道前驱）在单链表里做不到 $O(1)$——必须从头找前驱（$O(n)$）；双向链表没这问题（D3）。

关联 · 复杂度（C2）：删除的 $O(1)$ 前提是"已知前驱"；只给节点本身时单链表要 $O(n)$ 找前驱。

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

解析：链表没有下标，访问第 $k$ 个节点必须从头走 $k$ 步（$O(k)$，最坏 $O(n)$）。✅ C

排除法：A $O(1)$ 是数组的能力；B 排序与访问无关；D 下标语法是数组的。

关联 · 随机访问对比（C1）：数组 a[k] $O(1)$ vs 链表走 $k$ 步——"随机访问"是数组的独门优势。

考点：随机访问对比（C1）。

解析：数组连续存储，a[k] 的地址 = 首地址 + k×大小，直接算出（$O(1)$）；链表只能从头走（$O(n)$）。✅ 正确

排除法：无（判断题）。混淆点：vector 也是连续存储，同样支持 $O(1)$ 下标——连续性是随机访问的前提。

关联 · 内存连续（C7）：连续 → 可计算地址；分散 → 只能沿链走——结构决定复杂度。

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

解析：已知位置指针时，链表插入/删除只改指针（$O(1)$），不用移动任何元素。✅ 正确

排除法：无（判断题）。混淆点：前提是"已知位置"——找位置本身可能要 $O(n)$（见 C4）；"已知位置"后的增删才是 $O(1)$。

关联 · 数组对比（C3）：数组中间插入要移动 $O(n)$ 个元素——"增删快"是链表对数组的核心优势。

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

解析：数组连续存储，中间插入要把它后面的元素整体后移，最坏移动 $O(n)$ 个。✅ B

排除法：A $O(1)$ 是链表（已知位置）的开销；C $\log n$ 无来源；D $n^2$ 是排序等场景。

关联 · 链表插入（C2）：数组增删 $O(n)$（移动）、链表增删 $O(1)$（改指针）——"中间增删多"选链表（H1）。

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

解析：无序链表查找 = 从头逐个比，$O(n)$。✅ 正确

排除法：无（判断题）。混淆点：数组查找无序也是 $O(n)$（有序才能二分 $O(\log n)$）——查找不是链表的强项。

关联 · 查找（B2）：链表"查得慢、改得快"；数组"查得快（下标）、改得慢"——各有取舍（H1）。

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

解析：单链表头插/头删只动头指针（$O(1)$）；尾插/尾删要遍历到尾部（$O(n)$，除非维护尾指针）。✅ 正确

排除法：无（判断题）。混淆点：尾删比尾插更麻烦——尾删还要找到倒数第二个节点把它的 next 置空。

关联 · 尾插（B4）：维护 tail 指针或带尾指针循环链表（E4）能让尾部操作也变 $O(1)$。

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

解析：在中间反复插入删除（已知位置）：链表只改指针 $O(1)$；数组每次移动 $O(n)$ 个元素——链表明显更快。✅ A

排除法：B 把两者记反；C 移动 vs 改指针不可能一样；D 可比较。

关联 · 场景选择（H1）：判断标准 = 操作类型：频繁增删用链表、频繁随机访问用数组。

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

解析：数组一次性分配连续内存；链表节点逐个 new，分散在堆上。✅ 正确

排除法：无（判断题）。混淆点：链表分散 → 缓存不友好（访问相邻节点要跳内存）；数组连续 → 缓存友好——现代计算机上数组常更快。

关联 · 物理不连续（A3）：连续性带来随机访问（C1），也带来增删移动代价（C3）——一体两面。

考点：双向链表节点（D1）。

解析：双向链表节点两个指针域：prev（前驱）+ next（后继）：struct Node { int val; Node *prev, *next; };。✅ 正确

排除法：无（判断题）。混淆点：prev 和 next 都要维护——插入删除要改的指针翻倍（D2）。

关联 · 单向节点（A1）：单链表 1 个指针、双向 2 个——"多一根指针，多一份便利与开销"。

考点：双向插入（D2）。

解析：在 p 后插入 q：① q->prev = p ② q->next = p->next ③ p->next->prev = q ④ p->next = q——4 个指针。✅ C

排除法：A $1$/B $2$ 是单链表的数量；D $8$ 无来源。

关联 · 双向删除（D3）：插入 4 根、删除 2 根——双向的"删除省事、插入费事"。

考点：双向删除（D3）。

解析：删除 q：q->prev->next = q->next; q->next->prev = q->prev;——前驱后继直接互连，无需找前驱（改 2 根指针）。✅ 正确

排除法：无（判断题）。混淆点：单链表删除要 $O(n)$ 找前驱（B6）；双向删除节点本身即可 $O(1)$——这是双向的核心优势。

关联 · 找前驱（D5）：双向删除/找前驱 $O(1)$，单链表 $O(n)$——LRU 缓存选双向链表的原因（F4）。

考点：逆序遍历（D4）。

解析：双向链表从 tail 出发沿 prev 走，即可从尾到头遍历（$O(n)$），单链表做不到。✅ 正确

排除法：无（判断题）。混淆点：单链表逆序遍历要先反转（$O(n)$ 空间/时间）或用递归栈——双向是"天然可逆"。

关联 · 遍历（B1）：正向走 next、反向走 prev——双向链表正反自如。

考点：双向优势（D5）。

解析：双向链表有 prev 指针，找某节点的前驱直接 $O(1)$；单链表得从头走到该节点前一个（$O(n)$）。✅ 正确

排除法：无（判断题）。混淆点：找"后继"两者都 $O(1)$（都有 next）；区别在前驱。

关联 · 双向删除（D3）：前驱 $O(1)$ → 删除 $O(1)$——"找前驱"能力是双向一切优势的源头。

考点：双向代价（D6）。

解析：每个节点多一个 prev 指针（8 字节），$n$ 个节点多 $O(n)$ 空间——空间换时间。✅ 正确

排除法：无（判断题）。混淆点：空间翻倍（多 1/2 指针）换来前驱 $O(1)$——大数据量时要权衡。

关联 · 空间复杂度（ALG-56）：双向 vs 单向：时间上删除/逆序更快，空间上多 $O(n)$。

考点：哨兵节点（D7）。

解析：哨兵（哑）节点是链表头部的空壳节点（不存数据）：头插、头删、空表处理统一成"普通操作"，少写边界特判。✅ 正确

排除法：无（判断题）。混淆点：哨兵节点 ≠ 头指针；头指针仍指向哨兵；遍历时跳过哨兵。

关联 · 哑节点（G1）：处理头尾边界统一化——"空表也有一个固定节点"，删除/插入不再分"是否头节点"。

考点：循环链表定义（E1）。

解析：循环链表：尾节点的 next 指向头节点（或第一个节点），形成环。✅ 正确

排除法：无（判断题）。混淆点：循环链表没有 nullptr 结尾——遍历终止条件要换（E2）。

关联 · 尾节点（A5）：单链表尾节点 next 为空、循环链表尾节点 next 指向头——"空 vs 回头"是两者的分水岭。

考点：循环遍历终止（E2）。

解析：循环链表永远没有 nullptr，用 while (p != nullptr) 会死循环——通常记录起始节点，回到起点即停（或计数 n 次）。✅ 正确

排除法：无（判断题）。混淆点：判空条件是单链表的；循环链表用"是否回到起点/走了 n 步"判断。

关联 · 死循环（H3）：循环链表遍历条件写错是经典 bug——用 do-while + 回到 head 停止。

考点：约瑟夫问题（E3）。

解析：约瑟夫问题：n 人围圈报数出列——围圈结构天然是循环链表，删除出列者 $O(1)$。✅ 正确

排除法：无（判断题）。混淆点：数组模拟要反复移动/标记，循环链表直接"报数 + 删节点"最自然。

关联 · 删除（B6）：约瑟夫 = 循环链表 + 已知位置删除——两个 $O(1)$ 操作反复执行。

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

解析：循环链表尾节点 next 指向头，所以知道尾就能 O(1) 找到头——尾指针 + 循环 = 尾插 $O(1)$。✅ 正确

排除法：无（判断题）。混淆点：普通单链表尾插要遍历（B4）；循环链表让"头尾一家"，尾指针一举两得。

关联 · 队列实现（F2）：带尾指针的循环链表是"链表队列"的经典实现——头删尾插都 $O(1)$。

考点：快慢指针判环（E5）。

解析：快指针每次 2 步、慢指针 1 步：若有环，快指针最终会追上慢指针（相遇）；无环则快指针先到 nullptr。✅ 正确

排除法：无（判断题）。混淆点：判环不是"快指针绕一圈"——快慢相遇是标准判环法（弗洛伊德判圈）。

关联 · 快慢指针（G5）：同一技巧两用：判环（E5）+ 找中间节点（G5）。

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

解析：循环链表成环，从任意节点出发沿 next 走都能回到自身，即遍历全部节点。✅ 正确

排除法：无（判断题）。混淆点：单链表从中间节点出发只能访问后半段——"任意入口可遍历全部"是循环结构独有的。

关联 · 循环定义（E1）：环 = 处处连通——循环链表常用于轮转调度（Round-Robin）。

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

解析：栈 = 头插头删：入栈（push）头插 $O(1)$、出栈（pop）头删 $O(1)$——链表天然适配。✅ 正确

排除法：无（判断题）。混淆点：用尾端做栈顶也行但尾操作 $O(n)$（无尾指针）——栈顶放在头部最省。

关联 · 头插（B3）/头删（C5）：栈顶 = 链表头——"后进先出"对应"头进头出"。

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

解析：队列 = 一端入一端出：出队用头删（$O(1)$），入队用尾插（$O(n)$，无尾指针）——所以单链表队列要维护尾指针。✅ 正确

排除法：无（判断题）。混淆点：不维护尾指针的链表队列入队 $O(n)$，退化；维护尾指针（或循环链表）才双 $O(1)$。

关联 · 尾指针循环链表（E4）：头删 + 尾指针尾插 = 链表队列的标准形态。

考点：链地址法（F3）。

解析：哈希冲突的链地址法：每个桶挂一条链表，冲突元素链在一起。✅ 正确

排除法：无（判断题）。混淆点：开放定址法（线性探测）是另一方案，不用链表——两种解决冲突的思路。

关联 · 链表查找（C4）：链地址法下查找 = 哈希定位桶 + 链内 $O(1)$~$O(n)$ 查找——哈希表性能依赖负载因子。

考点：LRU 缓存（F4）。

解析：LRU（最近最少使用）：哈希表定位 $O(1)$ + 双向链表维护访问顺序（访问/插入移到头部、淘汰尾部）——两者结合全部 $O(1)$。✅ 正确

排除法：无（判断题）。混淆点：单链表删尾部节点要 $O(n)$ 找前驱——所以 LRU 用双向链表（D3 删除 $O(1)$）。

关联 · 双向删除（D3）：LRU 淘汰 = 删尾节点，双向链表删节点 $O(1)$——"哈希+双向链表"是 LRU 的标准答案。

考点：链表归并排序（F5）。

解析：归并排序只要"取中间 + 合并有序链"（不需随机访问），适合链表；时间复杂度 $O(n \log n)$、空间 $O(\log n)$（递归栈）。✅ 正确

排除法：无（判断题）。混淆点：快排需要随机访问基准（链表上退化）；堆排需要下标——归并是链表排序首选。

关联 · 快慢指针（G5）：找链表中间节点（分治）用快慢指针——归并排序的"分"就靠它。

考点：链表反转（F6）。

解析：反转 = 逐个把 next 掉头（记录前驱/当前/后继三指针），一趟 $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：反转不改节点内容，只改指针方向；递归写法同样 $O(n)$（栈深 n）。

关联 · 指针操作（G2）：反转的三指针（pre/cur/nxt）是链表指针操作的经典练习——"先存后继，再改方向"。

考点：哑节点（G1）。

解析：哑节点（dummy）作为链表头部的空壳：头插变"在哑节点后插"、删除头节点变"普通删除"——边界特判统一化。✅ 正确

排除法：无（判断题）。混淆点：哑节点不存数据、不影响遍历（从 dummy->next 开始）；它与哨兵节点（D7）是同一思想的两种叫法。

关联 · 哨兵节点（D7）：哨兵/哑节点 = "永远有一个前驱"——删除、插入不再检查"是不是头"。

考点：指针修改顺序（G2）。

解析：插入/反转等操作，先让新指针连好目标，再断开旧链——顺序反了会丢失节点（见 H4）。✅ 正确

排除法：无（判断题）。混淆点：没有"唯一正确顺序"，但要保证"每一步都不丢节点"——先连后断是通用安全顺序。

关联 · 插入顺序（H4）：q->next = p->next; p->next = q;——第二句覆盖前先备份好，节点不丢。

考点：释放内存（G3）。

解析：new 的节点不用了要 delete 释放，否则内存泄漏（堆空间只增不减）。✅ 正确

排除法：无（判断题）。混淆点：delete 只释放节点内存，指针变量还在（变悬垂，见 G4）；删除整表要循环 delete。

关联 · 动态内存（A4）：new/delete 配对——链表每建一个节点就欠一块堆内存，不还就泄漏。

考点：悬垂指针（G4）。

解析：delete p 后 p 指向已释放内存——再解引用是未定义行为（可能崩溃/数据错乱）；应置 p = nullptr。✅ 正确

排除法：无（判断题）。混淆点：delete 不会自动清空指针；释放后置空是标准安全习惯。

关联 · 空指针（第 4 章 F4）：悬垂指针比空指针更危险——空指针判空能拦住，悬垂指针判空也拦不住。

考点：快慢指针找中间（G5）。

解析：快指针走 2 步、慢指针走 1 步：快指针到末尾时，慢指针恰好在中间（奇数正中、偶数偏左）——$O(n)$ 一趟。✅ 正确

排除法：无（判断题）。混淆点：先数长度再走一半是两趟 $O(n)$；快慢指针一趟搞定。

关联 · 判环（E5）：同一"快慢指针"思想：判环看相遇、找中点看落位。

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

解析：两个指针一前一后（间隔 k 步）同步前进：前指针到末尾时，后指针正好在倒数第 k 个——一趟 $O(n)$。✅ 正确

排除法：无（判断题）。混淆点：先数总长再走 n-k 是两趟；双指针一趟——"间隔固定"技巧。

关联 · 快慢指针（G5）：快慢 = 速度差；前后 = 距离差——都是"两个指针一趟扫描"的变体。

考点：场景选择（H1）。

解析：频繁在中间插入/删除 → 链表（改指针 $O(1)$，免移动）；频繁随机访问/二分 → 数组。✅ D

排除法：A 随机访问是数组强项；B 二分需要 $O(1)$ 下标（数组）；C 连续存储是数组特征。

关联 · 复杂度对比（C 组）：选型口诀：查多用数组、改多用链表——看操作"读多还是写多"。

考点：头插顺序（H2）。

解析：头插每次把新节点放最前：插 1 → [1]；插 2 → [2,1]；插 3 → [3,2,1]——结果逆序。✅ B

排除法：A 是尾插的结果；C/D 顺序混乱。

关联 · 头插法（B3）：头插 = 逆序录入——"要正序就用尾插、要逆序就头插"。
验算：插 3 时 3->next = 头(2)、头 = 3 → 3→2→1 ✓

考点：循环链表死循环（H3）。

解析：循环链表没有 nullptr，while (p != nullptr) 永远为真 → 死循环。✅ 正确

排除法：无（判断题）。混淆点：用"回到起点/计数 n 次/do-while 先走再看"终止（见 E2）。

关联 · 遍历终止（E2）：循环链表遍历三选一：记起点、数 n 步、或先执行后判断。

考点：插入指针顺序（H4）。

解析：正确顺序：先 q->next = p->next（保存后继），再 p->next = q。若先执行 p->next = q，原后继丢失，链表断裂。✅ A

排除法：B 先 p->next = q 再 q->next = p->next 会让 q 指向自己（断链）；C 把 q 接到 p 前面；D 丢失 q 后的链。

关联 · 指针顺序（G2）：口诀"先连新、后断旧"——任何指针修改前先想"断了还能找到吗"。
验算：q->next = p->next; p->next = q; → 1→2→3 ✓

考点：综合判断（H5）。

解析：C 错误——链表没有随机访问，按下标访问是 $O(n)$（要遍历），$O(1)$ 是数组的能力。✅ C

排除法：A 链表物理不连续（A3）；B 已知位置指针时插入删除 $O(1)$（C2）；D 双向链表多一个指针（D6）——A/B/D 都正确。

关联 · 本章串联：A（存储 A3）、B（复杂度 C2）、C（随机访问 C1）、D（双向 D6）——综合题 = 细节判断的集合。

考点：静态链表结构（I1）。

解析：静态链表（数组模拟链表）用两个数组：val[i] 存节点 $i$ 的值、nxt[i] 存节点 $i$ 的下一个节点下标；nxt[i] == -1 表示 $i$ 是尾节点（没有后继）。✅ 正确

实现要点：静态链表 = 两个数组 + 一个 head 变量：val[i] 存值、nxt[i] 存后继下标、-1 相当于指针版的 NULL——所有"指针操作"都变成数组下标操作，遍历/插入/删除的逻辑与指针版一一对应。

排除法：无（判断题）。混淆点：-1 相当于指针链表里的 NULL——"空"的统一表示。

关联 · 尾节点（A5）：指针链表尾节点 next = NULL、静态链表尾节点 nxt = -1——同一个意思的两种写法。
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

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

解析：静态链表没有真正的"指针"，head 是一个 int 下标，指向第一个节点在数组中的位置；head = -1 表示空链表。✅ 正确

实现要点：静态链表的 head 是 int 下标，不是节点本身——它只回答"第一个节点在哪"。读静态链表代码时，把所有"指针"在脑中替换成"下标"，代码立刻可读。

排除法：无（判断题）。混淆点：head 不是节点、不是值——它是"第一个节点的下标"，与指针链表的 Node *head 地位相同。

关联 · 头指针（A2）：指针版 head 存地址、静态版 head 存下标——"入口标识"的两种实现。
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

考点：静态链表遍历（I3）。

解析：nxt = {1,2,3,4,-1} 表示 0→1→2→3→4，按 nxt 依次走：val[0]=10, val[1]=20, ..., val[4]=50，到 -1 停。✅ A

实现要点：静态链表遍历 = for (i = head; i != -1; i = nxt[i])——与指针版 for (p = head; p != NULL; p = p->next) 完全同构，nxt[i] 就是 p->next。

排除法：B 是逆序（nxt 反着走）；C 漏了最后一个（循环条件错）；D 输出的是下标。

关联 · 遍历（B1）：静态链表遍历与指针版完全同构：i = nxt[i] 就是 p = p->next。
验算：0→1→2→3→4→-1，输出 10 20 30 40 50 ✓
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

考点：静态链表插入（I4）。

解析：在 p 后插 q：先把 q 连到 p 的后继（nxt[q] = nxt[p]），再让 p 指向 q（nxt[p] = q）——与指针版"先连新、后断旧"一致。✅ A

实现要点：静态链表插入 = 先连后断：nxt[q] = nxt[p]; nxt[p] = q;——与指针版插入逐字同构（先保存后继、再接新节点），下标只是指针的另一种写法。

排除法：B 先 nxt[p] = q 再 nxt[q] = nxt[p] 会让 q 指向自己（断链，见 P1）；C 只改一根指针丢后继；D 把 q 插到了 p 前面。

关联 · 插入顺序（H4）：静态链表和指针链表的插入顺序完全一样——先保存后继，再接入新节点。
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

考点：静态链表删除（I5）。

解析：删除 = 让前驱的 nxt 跳过被删节点（nxt[p] = nxt[q]）；被删下标可加入"空闲链表"（free list）供后续插入复用。✅ 正确

实现要点：静态链表删除 = 前驱跳过被删节点：nxt[p] = nxt[q]——被删下标可加入空闲链表复用；"删除"本质是改链接，不是清数据。

排除法：无（判断题）。混淆点：静态链表的"删除"不真正清除数据，只是从链上摘掉；回收是可选优化。

关联 · 删除（B6）：指针版删除要 delete 释放、静态版回收下标——都是"资源管理"。
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

考点：静态链表长度受限（I6）。

解析：静态链表用固定数组存储节点，数组大小定义时已确定——长度上限 = 数组大小，无法随意动态增长；指针链表用 new 逐个分配，理论上只受内存总量限制。✅ 正确

实现要点：静态链表是"定长数组 + 逻辑链接"：数组多大、链表多长——容量上限在定义时就锁死；这也是它与指针链表最本质的差别。

排除法：无（判断题）。混淆点："省空间"不能一概而论——静态链表的下标类型由实现决定：int（4 字节）比 64 位指针（8 字节）省；但若用 long long 存下标（8 字节）则与指针相当——省不省取决于下标类型，不能作为静态链表的定论优点（本题不以此设问）。

关联 · 静态链表结构（I1）：nxt[i] 存的是下标——下标类型（int/long long）决定"省空间"结论。
关联 · 长度动态（A4）：指针链表动态增长 vs 静态链表定长——"能否随意增长"才是两者最本质的取舍。
大纲注：数组模拟链表在 NOI 2025 大纲中未单列，挂靠链表【3】的表示方式，属 J 复赛常用写法。

考点：头插构建（J1）。

解析：头插：nxt[cnt] = head; head = cnt;——每次把新节点放最前。插 1 → [1]；插 2 → [2,1]；插 3 → [3,2,1]。输出 3 2 1。✅ A

实现要点：头插构建 = 每次把新节点放最前：nxt[cnt] = head; head = cnt;——"后插的在前"，所以依次插 1,2,3 得到 3→2→1（逆序）。

排除法：B 是尾插结果；C/D 值重复（误以为 val 覆盖）。

关联 · 头插顺序（H2）：静态链表头插与指针版行为一致——"后插的在前"，结果逆序。
验算：3→2→1 ✓

考点：尾插构建（J2）。

解析：尾插维护 tail：nxt[tail] = cnt 接上新节点，再 tail = cnt。依次插 1、2、3 → 1 2 3。✅ B

实现要点：尾插构建 = 维护 tail 指针：nxt[tail] = cnt; tail = cnt;——有了 tail，尾插从 $O(n)$ 变 $O(1)$；tail 必须跟随新节点更新（忘更新是经典 bug）。

排除法：A 是头插；C 值重复；D 只输出两个（tail 更新错）。

关联 · 尾插（B4）：维护 tail 指针后尾插 $O(1)$——静态链表同样适用。
验算：1→2→3 ✓

考点：删除指定值（J3）。

解析：遍历找前驱 p：若 val[nxt[p]] == 2，令 nxt[p] = nxt[nxt[p]] 跳过节点 2。链表 1→2→3→4 删 2 后：1→3→4。✅ A

实现要点：删除指定值 = 遍历找前驱 + 改前驱的 nxt 跳过目标——"查找"与"指针修改"的组合；注意检查 nxt[p] != -1 防止访问尾后。

排除法：B 没删掉（跳过逻辑错）；C 删了 4；D 删了 1。

关联 · 删除（B6）：删除指定值 = 找前驱 + 改指针——"值查找"与"指针修改"的组合。
验算：p=0 时 nxt[0]=1, val[1]=2 → nxt[0]=nxt[1]=2 → 0→2→3：1 3 4 ✓

考点：反转（J4）。

解析：三指针法：t 暂存后继、nxt[cur] = pre 掉头、pre/cur 前进。1→2→3 反转后 3→2→1。✅ A

实现要点：链表反转 = 三指针法：t 保存原后继 → nxt[cur] = pre 掉头 → pre/cur 前进——口诀"存-改-走"，缺了 t 就丢链（静态链表/指针版通用）。

排除法：B 未反转；C/D 顺序混乱。

关联 · 反转（F6）：静态链表反转与指针版完全相同的逻辑——nxt 就是 next。
验算：cur=0: nxt[0]=-1；cur=1: nxt[1]=0；cur=2: nxt[2]=1；head=2 → 3 2 1 ✓

考点：遍历求和（J5）。

解析：沿 nxt 遍历累加：$1+2+3+4 = 10$。✅ A

实现要点：链表求和 = 遍历累加——与数组版唯一区别是跳转方式（nxt 代替 i++）；遍历 + 累加是链表第一基本功。

排除法：B $24$ 是连乘（$1\times2\times3\times4$）；C $4$ 是节点数；D $1$ 只加了头。

关联 · 遍历求和（第 6 章 A5）：数组用下标循环、链表用 nxt 跳——遍历求和的"链表版"。

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

解析：遍历计数器：0→1→2→3→-1 共 4 个节点。✅ B

实现要点：统计节点数 = 遍历 + cnt++——链表版"数个数"，与求和、找最值并称遍历三件套。

排除法：A $3$ 漏了最后一个；C $5$ 把数组大小当节点数；D $7$ 是头节点值。

关联 · 遍历（B1）：计数 = 遍历 + cnt++——链表基础操作三件套（数个数、求和、找最值）。

考点：找最大值（J7）。

解析：mx = val[0] 初始化，从第二个节点开始比：3,1,4,2 中最大 4。✅ A

实现要点：找最大值 = 以头节点值为初值，从第二个节点逐个比较——一趟 $O(n)$；找最值、求和、计数都是"遍历 + 维护一个变量"。

排除法：B $3$ 是头节点值；C $2$ 是最后一个；D $1$ 是最小值。

关联 · 找最值（A7）：数组与链表找最值同为 $O(n)$——链表版只是换遍历方式。

考点：统计奇数个数（K1）。

解析：val[i] % 2 == 1 计数：3、1、7 是奇数，4、2 不是——共 3 个。✅ B

实现要点：条件计数 = 遍历 + if 判断——"遍历 + 条件"是万能组合，换个条件（奇数/偶数/大于 x）就是新题。

排除法：A $2$ 漏了 7；C $4$ 把 2 也算了；D $5$ 全算。

关联 · 取模（第 4 章 C1）：% 2 == 1 判奇偶——链表遍历里套条件判断是阅读程序常考组合。

考点：找第 k 个节点（K2）。

解析：cur = 0 是第 1 个，循环 k-1 次走 nxt：第 3 个 = 走 2 步 = nxt[nxt[0]] = 下标 2 → val[2] = 30。✅ A

实现要点：找第 k 个节点 = 从头走 k-1 步（链表没有下标）——cur 从 0 出发，循环 i < k 走 nxt；与数组 a[k-1] 对应。

排除法：B $20$ 是第 2 个；C $40$ 是第 4 个；D $10$ 是第 1 个。

关联 · 访问第 k 个（B7）：链表"第 k 个"必须从头走 k-1 步——代码与概念一一对应。

考点：倒数第 k 个（K3）。

解析：双指针：q 先走 k 步，然后 p、q 同步走，q 到末尾时 p 在倒数第 k 个。k=2：p 最后指向下标 3 → val[3] = 4。✅ A

实现要点：倒数第 k 个 = 双指针：q 先走 k 步，然后 p、q 同步走，q 到末尾时 p 恰在倒数第 k——"间隔固定"一趟 $O(n)$。

排除法：B $5$ 是倒数第 1；C $3$ 是倒数第 3；D $2$ 无来源。

关联 · 双指针（G6）："间隔 k 步的双指针"是找倒数位置的经典——一趟 $O(n)$。

考点：判断递增（K4）。

解析：比较相邻：val[i] >= val[nxt[i]] 时置 ok = false。1<3<5<7 全部满足严格递增 → ok 保持 true，输出 YES。✅ A

实现要点：判断递增 = 比较相邻：val[i] >= val[nxt[i]] 即非递增——遍历 + 相邻比较，注意循环边界 nxt[i] != -1（别越到尾后）。

排除法：B 记反；C 输出的是布尔值不是 1；D 语法合法。

关联 · 有序去重（第 6 章 C6）："比较相邻"是链表/数组有序性判断的统一手法。

考点：统计大于 x（K5）。

解析：5,2,8,3,9 中大于 4 的：5、8、9——共 3 个。✅ C

实现要点：统计大于 x = 遍历 + 逐值比较——与 K1 同一模板；> 与 >= 的边界是常见陷阱。

排除法：A $1$ 只算 8；B $2$ 漏 5；D $4$ 把 4 也算（>= 与 > 混淆）。

关联 · 遍历统计（K1）：统计 = 遍历 + 条件计数——换个条件就是新题。

考点：链表平均值（K6）。

解析：和 $2+4+6+8 = 20$，个数 4，s / n = 20 / 4 = 5（整数除法）。✅ A

实现要点：链表平均值 = 一趟同时维护"和"与"个数"，最后 s / n——注意 int/int 整除，要小数需 s * 1.0 / n。

排除法：B $20$ 是和；C $4$ 是个数；D $6$ 是中间值记混。

关联 · 整型除法（第 3 章 D3）：s / n 是 int/int——想保留小数要 s * 1.0 / n。

考点：最大与最小差（K7）。

解析：最大值 9、最小值 2，差 $9 - 2 = 7$。✅ A

实现要点：最大最小差 = 一趟同时维护 mx 和 mn（两个变量都从 val[0] 起步）——"一次遍历多个统计"的写法，比两次遍历省一半时间。

排除法：B $9$ 是最大值；C $2$ 是最小值；D $5$ 是 $(9+2)/2$ 之类。

关联 · 找最值（A7）：一趟遍历同时维护 mx 和 mn——"一次遍历多个统计"的写法。

考点：指针反转（L1）。

解析：三指针反转 1→2→3→4：每个节点 next 掉头，最终 head 指向原尾节点 4，输出 4 3 2 1。✅ A

实现要点：指针反转 = 三指针（pre/cur/t）：t 保存后继、cur->next 掉头、指针前进——与 J4 静态链表版同一算法，next 就是 nxt。

排除法：B 未反转；C/D 顺序错乱。

关联 · 反转（F6）：与 J4（静态链表版）同一算法——t 保存后继是关键。

考点：删除偶数（L2）。

解析：1→2→3→4→5 删除值为偶数的节点（2、4），剩 1、3、5。✅ A

实现要点：删除偶数 = 遍历找前驱 + 条件删除（val[nxt[p]] 为偶数则 nxt[p] = nxt[nxt[p]]）——"删除满足条件的节点"通用模式：找前驱 → 判断 → 改链接。

排除法：B 是"只留偶数"；C 没删；D 顺序错。

关联 · 删除指定值（J3）：删除满足条件的节点 = 遍历找前驱 + 改 next——条件换成"偶数值"而已。

考点：头插建链输出（L3）。

解析：for (i = 5; i >= 1; i--) 依次头插 5、4、3、2、1：头插逆序，所以最终链表 1→2→3→4→5。✅ A

实现要点：头插建链 = 循环逆序头插：for (i = n; i >= 1; i--) 头插得到正序链表——"逆插正出"是头插的经典反直觉点，画链验证最稳。

排除法：B 是插入顺序（5 4 3 2 1）不是链表顺序；C/D 混淆。

关联 · 头插顺序（H2）：循环从大到小头插 = 得到从小到大——"逆序插入 = 正序输出"是经典反直觉点。
验算：插 5→[5]；插 4→[4,5]；…；插 1→[1,2,3,4,5] ✓

考点：删除倒数第 2 个（L4）。

解析：1→2→3→4→5 的倒数第 2 个是 4：删除后 1→2→3→5。✅ A

实现要点：删除倒数第 2 = 双指针找其前驱（倒数第 3 个）+ 改 next 跳过——"找位置"与"改链接"两段式。

排除法：B 删了最后一个 5；C 删了 3；D 删了 2。

关联 · 倒数第 k（K3）：找倒数第 2 = 双指针先走 2 步；删除它 = 改前驱的 next。

考点：两两交换（L5）。

解析：相邻两两交换：1↔2、3↔4 → 2 1 4 3。✅ A

实现要点：两两交换 = 相邻节点交换：先保存后继再改指针（防断链）——与插入一样守"先连后断"铁律。

排除法：B 未交换；C 是整体反转；D 只交换了前一对。

关联 · 指针操作（G2）：两两交换要小心断链——先保存后继再改指针是安全写法。

考点：有序插入（L6）。

解析：1→3→5 中插 4：找到 3（其 next 是 5 > 4），在 3 后插入 → 1→3→4→5。✅ A

实现要点：有序插入 = 找位置（p->next 的值 ≥ 新值时插入）+ 改两根指针——"插入排序"的链表版核心：查找 $O(n)$ + 插入 $O(1)$。

排除法：B 插到了 3 前（比较方向反）；C 插到了头；D 没插进去。

关联 · 指定位置插入（B5）：有序插入 = 找位置（$O(n)$）+ 插入（$O(1)$）——"插入排序"的链表版核心。

考点：删除重复（L7）。

解析：有序链表 1→2→2→3→3：相同值相邻，删除后每值留一个 → 1→2→3。✅ A

实现要点：有序去重 = 相邻比较：val[p] == val[nxt[p]] 时跳过重复——有序结构去重只需一趟，无序必须排序或哈希。

排除法：B 未去重；C 只留首尾；D 丢了 1。

关联 · 有序去重（第 6 章 C6）：有序结构去重 = 比较相邻——链表版只需改 next 跳过重复节点。

考点：双向正向遍历（M1）。

解析：p = p->next 从头走：1、2、3。✅ A

实现要点：双向正向遍历 = p = p->next 从头到尾——与单链表遍历相同；双向只是多了反向能力。

排除法：B 是 prev 反向走；C 指针没动（死循环式输出）；D 顺序错。

关联 · 双向遍历（D4）：正向走 next、反向走 prev——双向链表遍历的两种方向。

考点：双向反向遍历（M2）。

解析：p = p->prev 从 tail 走：3、2、1。✅ A

实现要点：双向反向遍历 = p = p->prev 从尾到头——单链表做不到（要反转或递归）；"可逆"是双向存在的意义。

排除法：B 正向；C/D 顺序错。

关联 · 逆序遍历（D4）：单链表逆序要反转或递归；双向链表直接沿 prev——这是双向存在的意义之一。

考点：循环链表走 n 步（M3）。

解析：循环链表 1→2→3→1→…：走 7 步依次是 1 2 3 1 2 3 1（每 3 步一轮，7 = 2×3+1）。✅ A

实现要点：循环链表走 n 步 = 有限次循环输出——每轮 3 个节点，7 步 = 2 轮 + 1；手算用取模规律（下标 i % 3）。

排除法：B 把步数当节点值；C 只走了一轮；D 循环链表有限步不会死循环。

关联 · 循环遍历（E2）：循环链表"走 n 步"恰好输出 n 个值——i % 3 的循环规律。
验算：7 步 = 1 2 3 1 2 3 1 ✓

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

解析：n=5、k=2（报到 2 出列）：2 出列 → 4 出列 → 1 出列 → 5 出列 → 剩 3。出列顺序 2 4 1 5 3。✅ A

实现要点：约瑟夫模拟 = 报数走 k-1 步 + 删除当前节点（改 next 跳过）——循环链表让"围圈"天然成立；每删一个节点少一次报数。

排除法：B 顺序出列（k=1）；C/D 报数方向或起点错。

关联 · 约瑟夫（E3）：循环链表 + 报数删除——每次报数走 k-1 步、删一个节点。
验算：围圈 1 2 3 4 5，报数：2 出 → 4 出 → 1 出 → 5 出 → 剩 3 ✓

考点：循环链表尾插（M5）。

解析：原链表 1→2→（回 1），tail = 2。插入 3：3->next = tail->next（即 1）；tail->next = 3；tail = 3。此时 tail->next = 1，从它开始输出 3 个：1 2 3。✅ B

实现要点：循环链表尾插 = tail->next 就是头（$O(1)$ 找到头）→ 新节点接入 → 更新 tail——"带尾指针的循环链表尾插 $O(1)$"是循环链表的最大红利。

排除法：A 3 1 2 是从新节点 3（tail 自身）开始输出；C 2 3 1 从旧 tail 开始；D 顺序错。

关联 · 带尾指针循环链表（E4）：循环链表尾插 $O(1)$——tail->next 永远能 $O(1)$ 找到头，插入后更新 tail 即可。
验算：插入后链 1→2→3→（回 1），tail=3，tail->next=1：输出 1 2 3 ✓

考点：判环代码（M6）。

解析：快慢指针判环：fast 每次 2 步、slow 每次 1 步。无环时 fast 会先到达 NULL（或 fast->next == NULL），循环正常退出返回 false——不会死循环。✅ 正确

实现要点：判环 = 快慢指针：fast 每次 2 步、slow 每次 1 步——有环则快指针必然追上慢指针（相遇）；无环则 fast 先撞 NULL。循环条件双判空（fast && fast->next）防解引用空指针。

排除法：无（判断题）。混淆点：fast->next->next 的解引用需要 fast != NULL && fast->next != NULL 双重判空——这正是循环条件的两个守卫；有环时快慢必相遇返回 true。

关联 · 快慢指针判环（E5）：判环代码的三要素：快 2 慢 1、双重判空、相遇即真。
记忆点：while (fast && fast->next)——"快指针走得快，先撞墙（NULL）就无环"。

考点：补全头插（N1）。

解析：头插 = 新节点 q 的 nxt 指向旧头，再让 head = q：nxt[q] = head。✅ A

实现要点：头插补全 = nxt[q] = head（新节点连旧头）——先连后换头：nxt[q] = head; head = q; 两行缺一不可。

排除法：B nxt[head] 是第二个节点；C 自指；D 直接断链（把 q 变成孤立尾）。

关联 · 头插（B3）：nxt[q] = head; head = q; 是头插标准两行——先连后换头。

考点：补全尾插（N2）。

解析：尾插：新节点接到 tail 后面（nxt[tail] = q），然后更新尾指针 tail = q。✅ A

实现要点：尾插补全 = tail = q（尾指针跟随新节点）——nxt[tail] = q 接链 + tail = q 更新，忘更新 tail 则尾插回到 $O(n)$。

排除法：B head 只在空表时用；C 自指（nxt[tail] 已是 q）；D 把 tail 置空。

关联 · 尾插（B4）：维护尾指针后，尾插 $O(1)$——tail 必须跟随新节点移动，忘更新是经典 bug。

考点：补全删除（N3）。

解析：删除 q（p 是前驱）：让 p 的 nxt 跳过 q 指向 q 的后继：nxt[p] = nxt[q]。✅ A

实现要点：删除补全 = nxt[p] = nxt[q]（前驱跳过被删节点）——"改前驱的 next 指向被删节点的后继"一句话就是删除的全部。

排除法：B 让 p 指向 q（没删）；C 自指；D 断掉整条链。

关联 · 删除（B6）：nxt[p] = nxt[q] 是删除的核心——q 从链上摘除（q 本身可以不管或回收）。

考点：补全反转（N4）。

解析：反转循环里 t 已保存当前节点的后继（t = nxt[cur]），掉头后 cur 要沿原后继前进：cur = t。✅ A

实现要点：反转补全 = cur = t（沿保存的原后继前进）——t 是"记忆原后继"的变量，掉头后没有它就无法前进（死循环）。

排除法：B pre 是已处理的前一个（会倒退）；C/D 都指向已修改的 nxt[cur]（死循环）。

关联 · 反转（F6）：三指针 t/pre/cur 中，t 是"记忆原后继"——没有它反转就会丢链。
记忆点：先存后继（t），再掉头，最后前进——"存-改-走"。

考点：补全查找（N5）。

解析：查找失败返回 -1（与静态链表"空"的约定一致，也便于调用方判断）。✅ A

实现要点：查找补全 = return -1（找不到的统一返回值）——与 -1 表示"空"的约定一致，调用方 if (find(...) != -1) 判断。

排除法：B 0 是合法下标（会与真实节点混淆）；C head 返回头指针；D i 越界。

关联 · 空表示（I1）：静态链表用 -1 表示"无"——查找失败、空链表、尾节点统一用它。

考点：补全计数（N6）。

解析：每访问一个节点计数加一：cnt++。✅ A

实现要点：计数补全 = cnt++（每访问一个节点加一）——遍历 + 计数器是链表最基础的功能实现。

排除法：B cnt = i 是下标赋值；C cnt = 1 每次重置；D i++ 改的是循环变量（且循环已自动前进）。

关联 · 统计节点数（J6）：遍历 + cnt++——计数是链表遍历的基本应用。

考点：补全建链（N7）。

解析：尾插建链：非空表时新节点接到 tail 后面：nxt[tail] = cnt；之后统一 tail = cnt。✅ A

实现要点：建链补全 = nxt[tail] = cnt（非空表时新节点接在旧尾之后）——尾插建链框架：空表设头 / 非空接尾，最后统一更新 tail。

排除法：B 方向反（新节点指向尾）；C 把 tail 变成新节点的 next；D 用 head 接（丢中间）。

关联 · 尾插（B4）：建链两分支：空表设 head、非空接 tail——然后都更新 tail。这是尾插建链的标准框架。

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

解析：栈顶在链表头部：push = 头插、pop = 头删。push 1、2、3 后链表 3→2→1，pop 依次出 3、2、1。✅ A

实现要点：链表实现栈 = 栈顶放头部：push = 头插、pop = 头删——两头操作都 $O(1)$；栈顶放尾部则要 $O(n)$ 找尾，得不偿失。

排除法：B 是队列顺序；C/D 顺序错。

关联 · 链表实现栈（F1）：头插头删 $O(1)$——栈用链表实现时栈顶必在头部。
验算：push 1→[1]；push 2→[2,1]；push 3→[3,2,1]；pop×3：3 2 1 ✓

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

解析：队列入 = 尾插、出 = 头删。入 1、2、3（1 在头），出队依次 1、2、3。✅ A

实现要点：链表实现队列 = 队头出（头删 $O(1)$）+ 队尾进（尾插需 tail 指针才 $O(1)$）——"头删尾插 + 尾指针"是链表队列的标准形态。

排除法：B 是栈顺序；C/D 顺序错。

关联 · 链表实现队列（F2）：队列 = 头删尾插（维护 tail）——"先进先出"。
验算：入 1→[1]；入 2→[1,2]；入 3→[1,2,3]；出队：1 2 3 ✓

考点：约瑟夫完整代码（O3）。

解析：n=5、k=2 的出列顺序 2、4、1、5，最后剩下 3。✅ A

实现要点：约瑟夫"最后剩下谁" = 把出列顺序完整走一遍，剩下的那个就是答案——模拟到最后只剩一个节点时停止。

排除法：B 1 是第 3 个出列的；C 5 是第 4 个出列的；D 2 是第一个出列的。

关联 · 约瑟夫（E3/M4）：约瑟夫"最后剩下谁"是高频问法——把出列顺序走完，剩下的就是答案。
验算：出列 2→4→1→5，剩 3 ✓

考点：邻接表（O4）。

解析：邻接表 = 每个顶点一条链表（存它的邻接点）——用数组模拟时就是"头结点数组 + 静态链表"，本质相同。✅ 正确

实现要点：邻接表 = 每个顶点一条链表存邻居——数组版即"头结点数组 + 静态链表"（head[i] 是顶点 i 第一条边的下标）；静态链表是图的存储基石。

排除法：无（判断题）。混淆点：邻接表是"图"的存储方式，但其内部结构就是链表——图论题里"数组模拟链表"常考此景。

关联 · 静态链表（I 组）：邻接表的数组版：head[i] 是顶点 i 的第一条边下标、nxt 串起其余边——静态链表活学活用。

考点：栈顶操作位置（O5）。

解析：栈顶放链表头部：头插（push）头删（pop）都 $O(1)$；若放尾部则要 $O(n)$ 找尾。✅ 正确

实现要点：栈顶放头部 = 头插头删 $O(1)$——"栈只要一端，就放最好操作的一端"；队列才需要一头一尾。

排除法：无（判断题）。混淆点：队列才需要"一头一尾"；栈只需要一端——放头部最省。

关联 · 链表实现栈（F1）：栈顶 = 链表头——"后进先出"对应"头进头出"。

考点：断链错误（P1）。

解析：p->next = q 先执行后，p->next 已是 q；再 q->next = p->next 让 q 指向自己——原链表 p 之后全部丢失。✅ 正确

实现要点：插入铁律"先连新、后断旧"：q->next = p->next 必须先执行——先断旧链则原后继失联，q->next = p->next 再执行会让 q 指向自己（自环）。

排除法：无（判断题）。混淆点：正确顺序是 q->next = p->next; p->next = q;（先连后断，见 H4）。

关联 · 插入顺序（H4）：插入铁律"先连新、后断旧"——违反它必然断链。
验算：p→(原后继 X)，先 p->next = q 后 X 失联，q->next = q 自环 ✓

考点：忘记更新头指针（P2）。

解析：头插必须 head = q 让新节点成为入口——不更新的话 head 仍指向旧头，q 成为孤立节点（无法从 head 到达）。✅ 正确

实现要点：头指针是链表的"入口"——头插后必须 head = q，否则新节点不可达（逻辑上不在链上，指针版还造成内存泄漏）。

排除法：无（判断题）。混淆点：内存上 q 存在，但逻辑上"不在链上"——q 不可达（若用指针版还造成内存泄漏）。

关联 · 头插（B3）：头插两行缺一不可：q->next = head（连）+ head = q（换头）。

考点：遍历条件错误（P3）。

解析：nxt[i] != -1 在当前节点是倒数第二个时就停止——最后一个节点（nxt 为 -1 的那个）不会被访问。✅ 正确

实现要点：遍历条件用"当前节点非空"（i != -1）——用"下一个非空"（nxt[i] != -1）会在倒数第二个节点提前停，漏掉尾节点。

排除法：无（判断题）。混淆点：正确条件是 i != -1（访问到末尾为止）；nxt[i] != -1 少访问最后一个。

关联 · 遍历（B1）：遍历条件用"当前节点非空"（i != -1）——用"下一个非空"会漏尾。
验算：1→2→3：i=0(nxt=1≠-1)访问1；i=1(nxt=2≠-1)访问2；i=2(nxt=-1)停止——3 没访问 ✓

考点：释放后使用（P4）。

解析：delete q 后 q 指向已释放内存，再 q->val 是悬垂指针（未定义行为）。✅ 正确

实现要点：delete 后指针变悬垂——释放后必须置 NULL（或不再使用）；悬垂指针判空也拦不住，比空指针更危险。

排除法：无（判断题）。混淆点：delete 不清空指针；释放后应置 q = NULL（见 G4）。

关联 · 悬垂指针（G4）：释放后使用 = 读已归还的内存——可能崩溃、可能读到脏数据。

考点：综合判断（P5）。

解析：nxt[1] = nxt[2]：nxt[2] 是 -1，所以节点 1 的后继从 2 改为 -1——节点 3（下标 2）从链上被跳过。链 0→1→(-1)，输出 1 2。✅ 正确

实现要点：综合判断题 = 逐句对照本章细节：nxt[p] = nxt[q] 改的是 p 的后继（跳过 q）——"改前驱、跳被删"是删除操作的静态链表写法。

排除法：无（判断题）。混淆点：nxt[1] = nxt[2] 改的是节点 1 的后继（不是节点 2 的）；节点 2 仍在链上（1→2），被跳过的是节点 3——"改前驱的 next 指向被删节点的后继"正是删除操作的静态链表写法（见 N3）。

关联 · 删除（N3）：nxt[p] = nxt[q]（p 是 q 的前驱）——本题 p=1, q=2，删的是下标 2 的节点 3。
验算：nxt[1] = nxt[2] = -1 → 0→1→-1，输出 1 2 ✓

题面说"删除下标 2 的节点 3"——对，节点 3（下标 2）被跳过 ✓。