📚 课程目录第4章数据结构与算法高频题

4. 数据结构与算法高频题

数据工程面试中，算法题常围绕链表、哈希表、二叉树、字符串、排序与动态规划展开。面试官不仅考察代码正确性，更关注数据结构选型、时空复杂度分析与边界条件处理。掌握通用回答框架，可以帮你在高压下稳定发挥。

面试问题	请实现一个函数，输入一个单链表头节点，反转链表并返回新头节点。
考察点	链表指针操作、迭代/递归思维、边界处理（空链表、单节点）
回答框架	1) 明确链表定义 2) 迭代法：三个指针（prev/curr/next） 3) 循环终止条件 4) 返回新头 5) 复杂度 O(n)/O(1)
示例回答	“我使用迭代法。定义 prev=null，curr=head，每次循环保存 next 指针，将 curr.next 指向 prev，然后移动 prev 与 curr。最后返回 prev 作为新头。时间复杂度 O(n)，空间 O(1)。” （60字）
可能追问	递归实现？如何判断链表有环？如果要求原地反转且不允许修改节点值怎么做？
避坑提醒	忘记更新 head 的 next 为 null 会造成循环链表；递归时注意栈溢出。

面试问题	给定一个整数数组 nums 和一个整数目标值 target，请找出和为目标值的两个整数，并返回它们的下标。
考察点	哈希表应用、时空权衡、一题多解（暴力/哈希/排序+双指针）
回答框架	1) 暴力枚举 O(n²) → 不推荐 2) 哈希表 O(n)：遍历时查 complement = target - nums[i] 3) 返回索引 4) 注意不能重复使用同一元素
示例回答	“我使用哈希表做一次遍历。遍历数组，检查 target − nums[i] 是否已在 map 中，若在则返回两个索引，否则将当前元素存入 map。时间 O(n)，空间 O(n)。相比暴力更优。” （78字）
可能追问	如果数组有序怎么办？返回所有组合？如果有重复元素怎么处理？
避坑提醒	返回索引而不是值；注意先检查 target − nums[i] 再存入当前元素（避免自己和自己配对）。

面试问题	给定一棵二叉树，请按层从上到下、从左到右返回节点值的二维数组。
考察点	BFS 模板、队列使用、按层分组技巧、空树处理
回答框架	1) 空树返回 [] 2) 初始化队列，根入队 3) while 队列非空：记录当前层长度 len，遍历 len 次出队、收集值、入队子节点 4) 每层结果加入最终数组
示例回答	“使用队列实现层序遍历。根节点先入队，while 循环中每轮先统计当前队列长度，弹出该长度个节点并记录值，同时将子节点入队。这样每轮对应一层。时间复杂度 O(n)，空间 O(n)。” （85字）
可能追问	如何实现 zigzag 层序遍历？用 DFS 如何做？如果树非常大如何优化空间？
避坑提醒	每层开始时一定要先记录当前队列大小，否则 pop 时队列长度会变化；注意子节点为空时不要入队。

  💡 提升技巧： 面试时先口述思路（选什么数据结构、复杂度多少），再写代码。遇到卡壳时主动问面试官“是否需要考虑大数/内存限制？”，展示工程思维。