📚 课程目录第4章高频技术面试题-数据结构与算法

4. 高频技术面试题 — 数据结构与算法

数据结构与算法是游戏客户端开发面试的“硬通货”，重点考察代码基本功、逻辑思维与性能敏感度。本章聚焦最高频的三大题型：链表操作、树遍历、哈希优化。掌握通用回答框架，才能在压力下稳定输出。

数据结构	高频题型	核心考点	常见公司
链表	反转、合并、环检测	指针操作、递归/迭代	腾讯、网易、米哈游
二叉树	层序、前中后序、最近公共祖先	递归/队列、遍历顺序	字节、完美世界、莉莉丝
哈希表 / 数组	两数之和、滑动窗口、去重	空间换时间、双指针	阿里巴巴、FunPlus、三七互娱
动态规划	背包、路径、状态压缩	状态定义、转移方程	字节、腾讯、网易

📌 问题1：反转单链表

面试官考察点：链表的指针操作熟练度、边界条件处理（空链表、单节点）、能否写出迭代 + 递归两种解法。

回答框架：

① 明确链表定义与输入输出；
② 迭代法：维护 prev/curr/next 三个指针，逐次反转；
③ 递归法：假设子链表已反转，将当前节点指向之前节点；
④ 复杂度：时间 O(n)，空间 O(1) / O(n)。

示例回答（60-100字）：

public ListNode reverseList(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

可能追问： 递归实现？反转 m 到 n 的区域？如何检测链表是否有环？如果链表很大，如何避免递归栈溢出？

⚠ 避坑提醒： 迭代时容易丢失 next 引用，必须先用临时变量保存；空链表和单节点要单独返回原头节点；递归解法注意返回新头节点。

📌 问题2：二叉树的层序遍历

面试官考察点：队列的使用能力、分层输出技巧（每层一个 List）、边界（空树）、BFS 思维。

回答框架：

① 判空，返回空列表；
② 使用 Queue，根节点入队；
③ 循环每层：获取当前队列 size，依次出队并加入 level 列表，同时子节点入队；
④ 将 level 加入结果集，返回 List<List<Integer>>。

示例回答（60-100字）：

public List> levelOrder(TreeNode root) {
    List> res = new ArrayList<>();
    if (root == null) return res;
    Queue q = new LinkedList<>();
    q.offer(root);
    while (!q.isEmpty()) {
        int size = q.size();
        List level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = q.poll();
            level.add(node.val);
            if (node.left != null) q.offer(node.left);
            if (node.right != null) q.offer(node.right);
        }
        res.add(level);
    }
    return res;
}

可能追问： 如何实现之字形层序遍历？用 DFS 如何实现？如果要求空间 O(1) 呢？

⚠ 避坑提醒： 必须用变量保存每层的节点数（queue.size()），因为循环中队列大小会变化；空指针判断优先进行。

📌 问题3：两数之和（无序数组）

面试官考察点：哈希表空间换时间的思维、处理重复元素、返回下标还是数值？能否给出 O(n) 解法？

回答框架：

① 明确要求：返回两个数的下标（假设只有一对答案）；
② 哈希表存储<值, 下标>，遍历数组；
③ 每次检查 target - nums[i] 是否在表中：存在则直接返回；不存在则将当前元素加入表；
④ 时间 O(n)，空间 O(n)。

示例回答（60-100字）：

public int[] twoSum(int[] nums, int target) {
    Map map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{map.get(complement), i};
        }
        map.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

可能追问： 如果有多个解怎么办？数组有序时如何优化（双指针）？要求返回所有不重复组合？

⚠ 避坑提醒： 一定要先查表再插入，避免同一个元素被重复使用（例如 target=6, 数组[3,3]）；如果返回数值而非下标，可以改用 HashSet 减少空间。

💡 面试加分提示： 回答时主动说“我先画个图演示指针变化”，面试官会认为你思路清晰；完成基础解法后主动提出优化方向（如递归改成迭代避免栈溢出），可用性思维更突出。

｜本章要点：锚定链表/树/哈希三大题型的回答框架，分步演示 + 边界覆盖 + 复杂度分析是通关关键｜