算法选择题：链表（5 题）
016 关于单链表按下标访问第 k 个节点，哪种表述准确？
难度： 基础
- A. 链表访问任意位置都是 O(1)，因为节点自带索引
- B. 链表插入恒为 O(1)，与是否持有前驱引用无关
- C. 需要从已知节点逐步移动 k 步，单次 O(k)；已经持有目标前驱引用时，局部插入可以是 O(1)
- D. 链表与数组一样支持 O(1) 下标访问
查看答案与解析
正确答案C
正确原因： 链表访问第 k 个节点需要从已知节点逐步移动；已经持有目标前驱引用时局部插入可以是 O(1)。
错误选项辨析： A 项：节点通常只保存值与后继引用，不保存下标；B 项：没有前驱引用时仍需先遍历到目标位置；D 项：链表节点没有下标索引，访问第 k 个必须逐个移动。
017 删除链表节点时使用虚拟头节点（哨兵）的主要目的是什么？
难度： 进阶
- A. 虚拟头节点会成为业务链表的一部分，遍历时需要统计它
- B. 统一处理“删除头节点”与“删除普通节点”的逻辑，避免对头节点的特判；返回结果时必须跳过哨兵本身
- C. 虚拟头节点能让所有节点访问都变成 O(1)
- D. 不使用虚拟头节点就无法删除任何节点
查看答案与解析
正确答案B
正确原因： 哨兵节点可统一处理头节点删除与普通节点删除；返回结果时必须跳过哨兵本身。
错误选项辨析： A 项：哨兵只是辅助节点，不属于业务数据，返回时必须跳过；C 项：哨兵只简化删除逻辑，不改变按位置访问的成本；D 项：不用哨兵也能删除，只是需要额外处理头节点特判。
018 判断两个链表是否相交，正确的依据是什么？
难度： 进阶
- A. 只要两个节点值相等，就能证明链表相交
- B. 相交判断只需比较值，引用比较在 C# 中不可用
- C. 两个链表相交一定意味着长度相同
- D. 相交与环检测通常比较节点引用而不是节点值；值相同的两个节点仍可能属于不同链表
查看答案与解析
正确答案D
正确原因： 链表相交与环检测通常比较节点引用而不是节点值；值相同的两个节点仍可能属于不同链表。
错误选项辨析： A 项：不同链表可能包含相同值的节点，值相等不代表共享节点；B 项：C# 中引用类型可用 ReferenceEquals 或 == 比较引用身份；C 项：相交链表的长度可以不同，相交发生在某个共同后缀之前。
019 用快慢指针判断链表是否有环时，快指针走两步之前必须保证什么？
难度： 进阶
- A. 必须保证 fast 与 fast.Next 均可访问，才能安全访问 fast.Next.Next；链表长度为奇/偶时快指针会分别停在末节点或 null
- B. 必须先完整计算链表长度，再决定能否走两步
- C. 快慢指针只适用于无环链表，有环时必须先排序
- D. 只需检查 fast 非 null，就能安全访问 fast.Next.Next
查看答案与解析
正确答案A
正确原因： 快指针走两步前必须保证 fast 与 fast.Next 可访问；奇偶长度会让快指针分别停在末节点或 null。
错误选项辨析： B 项：快慢指针不需要预知长度，只需在移动前检查指针可访问性；C 项：快慢指针正是为环检测设计，与排序无关；D 项：fast.Next 也可能为 null，访问 fast.Next.Next 会空引用。
020 迭代反转单链表时，为什么必须先保存原来的 next？
难度： 综合
- A. 反转只需交换头尾引用，不需要逐个处理节点
- B. 使用 while 循环反转时不需要任何指针变量
- C. 改写 current.Next 指向新前驱之前必须保存原来的 next，否则未处理的后缀将无法再访问，链表会断裂
- D. 先修改 Next 再保存原 next，也不影响后续节点
查看答案与解析
正确答案C
正确原因： 改写 current.Next 前必须先保存原来的 next；丢失 next 引用会让未处理后缀无法访问。
错误选项辨析： A 项：单链表反转必须逐个调整每个节点的 Next 方向；B 项：至少需要当前节点与前驱（以及临时保存的 next）指针；D 项：一旦改写了 Next，原后继引用就丢失了，无法继续遍历。