# 1. 删除链表的倒数第 N 个节点（LeetCode 19）中双指针间距 N 的一次遍历法，如何处理删除头节点的边界 A 若不使用虚拟头节点，删除头节点时直接返回 head.next 即可，无需任何特判 B 慢指针最终指向的正是待删除的节点本身 C 该算法需要遍历链表两次才能定位到待删节点 D 使用虚拟头节点可以把删除头节点的情形统一为修改前驱指针，避免边界特判 ✓ 正确答案
# 2. 单调队列如何 O(1) 均摊维护滑动窗口最大值（LeetCode 239），双端队列存候选下标、队首淘汰过期元素、队尾淘汰更小元素 A 队尾淘汰条件应为 nums[队尾] < nums[i]，即只淘汰严格更小的元素 B 队列中存值而非下标，否则无法判断元素是否过期 C 窗口最大值可以从队尾直接取得 D 每个元素入队出队各一次，总复杂度 O(n)，均摊到每步 O(1) ✓ 正确答案
# 3. 单链表归并排序如何实现 O(n log n) 时间 O(1) 空间？自顶向下与自底向上两种写法的取舍 A 自顶向下写法的额外空间为 O(n)，因为需要辅助数组 B 链表归并排序通过重排指针完成合并，无需 O(n) 辅助数组 ✓ 正确答案 C 自底向上写法的空间复杂度为 O(log n) D 链表无法使用归并排序，因为它不支持随机访问
# 4. 合并 K 个有序链表的最优复杂度是多少，优先队列与分治两种实现如何取舍？ A 分治法的时间复杂度为 O(NK) B 最优时间复杂度为 O(K log N)，取决于链表数量 C 优先队列法的时间复杂度为 O(N log N) D 最优时间复杂度为 O(N log K)，其中 N 为总节点数 ✓ 正确答案
# 5. 实现带随机指针链表的深拷贝，要求 O(n) 时间 O(1) 额外空间（原题 138），说明'插入-拆链'三步法的正确性 A 插入-拆链法的空间复杂度为 O(n)，因为需要哈希表 B 拆分时必须先恢复原链表再连接副本，否则 random 指向会丢失 C 副本节点的 random 应指向原节点 random 的后继节点 ✓ 正确答案 D 该算法需要遍历链表三次，总时间复杂度 O(n)
# 6. 用两个栈实现队列的均摊 O(1) 入队/出队，输出栈空时整堆翻转，势能法证明均摊代价 A 每次出队都必须把 inStack 全部翻转，因此出队最坏 O(n) B 每个元素最多被移入、翻转、弹出各一次，故均摊 O(1) ✓ 正确答案 C 入队操作在最坏情况下是 O(n) D 该实现无法保证元素的先进先出顺序
# 7. 链表插入排序与数组插入排序的复杂度差异中为何链表不需要移动元素但仍为 O(n²) A 链表插入排序因为不需移动元素，时间复杂度降为 O(n log n) B 链表插入排序最坏情况发生在已有序输入时 C 链表插入排序的插入位置查找是 O(1) D 链表插入排序的复杂度仍是 O(n²)，因为比较次数仍为 O(n²) ✓ 正确答案
# 8. 单链表每 k 个一组反转（LeetCode 25）中当剩余不足 k 时保持原序，给出迭代与递归两种实现并比较栈深 A 递归实现的递归深度为 O(n/k)，迭代实现为 O(1) ✓ 正确答案 B 递归实现的递归深度为 O(n)，与 k 无关 C 剩余不足 k 个节点时应当反转剩余部分 D 迭代实现的额外空间为 O(n)
# 9. 如何判断单链表是否回文？要求 O(n) 时间 O(1) 空间，找中点+反转后半+比较+恢复 A 反转后半段后逐节点比较，比较过程需 O(n) 时间 ✓ 正确答案 B 快慢指针找到的慢指针位置一定在后半段之后 C 需要借助 O(n) 的辅助数组存储节点值 D 该算法无法恢复原链表结构
# 10. 给定两个无环单链表，设计 O(1) 空间判断它们是否相交并找出第一个交点，给出正确性证明（长度差+双指针追赶） A 相交链表的交点之后部分完全相同，因此用长度差对齐后同步比较即可 ✓ 正确答案 B 双指针追赶法需要 O(n) 额外空间记录访问过的节点 C 若两链表不相交，双指针追赶法会陷入死循环 D 只需比较两个链表的头节点是否相同即可判定相交
# 11. LFU 缓存（LeetCode 460）的频次桶设计中需要'频次→同频节点双向链表'，minFreq 的维护如何做到 O(1)？ A 淘汰时总是删除频次桶中最早创建的节点 B minFreq 递增时需要扫描所有频次桶才能确定新最小值 C 访问某 key 时只需更新其值，无需改变其所在频次链表 D 频次桶内用双向链表是为了支持 O(1) 的插入与删除 ✓ 正确答案
# 12. LRU 缓存为什么用"哈希表+双向链表"，数组实现为什么不可行？ A 用数组实现即可在 O(1) 内完成访问顺序调整 B 哈希表提供 O(1) 定位，双向链表提供 O(1) 的移动与删除 ✓ 正确答案 C 淘汰时删除链表头节点即可 D 数组能更好地利用随机访问优势，因此是首选
# 13. Floyd 判环算法中，快慢指针相遇后，为何把一个指针移回 head 同速前进能在环入口相遇？给出严格的模长推导 A 第一次相遇点就是环入口 B 快慢指针相遇时，快指针一定比慢指针多走一圈 C 从相遇点继续走 a 步（a 为头到入口距离）恰回到环入口，因此与从头出发的指针同速相遇于入口 ✓ 正确答案 D 该算法依据 a+b 不是环长的整数倍来定位入口
# 14. 两个用逆序链表表示的非负整数相加（LeetCode 2）中如何处理进位与不等长，若改为正序存储（最高位在前）如何解决 A 正序存储时可以直接从头开始逐位相加 B 逆序存储（最低位在前）使逐位相加无需对齐低位 ✓ 正确答案 C 遍历结束后若 carry 为 1 应保留在最高位节点中，无需新增节点 D 两个链表长度不相等时，较长链表的高位部分应被忽略
# 15. 快慢指针求链表环的长度中相遇后继续同速前进到再次相遇的步数即环长，与 Floyd 判环入口推导的关联？ A 测环长时两个指针必须保持原速度差 B 环长等于从链表头到相遇点的距离 C 从首次相遇点出发，绕环一圈回到相遇点的步数即环长 ✓ 正确答案 D 环长与 Floyd 判环入口推导中的环长 L 无关
# 16. 如何判断链表是否存在环并找到环入口，要求 O(1) 空间（快慢指针法证明）？ A 环入口就是快慢指针第一次相遇的位置 B 相遇后把两个指针都移到 head 重新前进即可找到入口 C 该算法需要 O(n) 空间记录访问过的节点 D 无环时快指针会先到达末尾，据此判定无环 ✓ 正确答案
# 17. 用两个队列实现栈，每次入队后把前面所有元素重新排队，使新元素位于队首 A 入栈 O(1)，出栈 O(n) B 入栈和出栈都是 O(n) C 入栈和出栈都是 O(1) D 入栈 O(n)，出栈 O(1) ✓ 正确答案
# 18. 设计一个支持 getMin 的栈，辅助栈与差值法两种实现的空间复杂度对比？ A 辅助栈法与差值法的空间复杂度都是 O(n) ✓ 正确答案 B 差值法的空间复杂度为 O(1) C 辅助栈法在元素全递增时空间为 O(1) D 差值法比辅助栈法在渐进空间上更优
