🌳 数据结构
链表/栈/队列 · 哈希表 · 二叉树 · 堆 · 图，附手写代码
1. 链表常考操作？反转链表为什么是"基本功"？
链表考察点集中在：指针操作 + 边界条件。高频题：反转、找环（快慢指针）、找中点、合并、删除倒数第 N 个。写链表代码的铁律：
- 用 dummy 虚拟头节点处理头节点变化（删除/插入头）
- 画图推演，每次只动 2~3 个指针
- 注意 null 边界（链表为空、只有一个节点）
反转链表（迭代版，必背）
public ListNode reverseList(ListNode head) {
ListNode prev = null, cur = head;
while (cur != null) {
ListNode next = cur.next; // 1. 暂存后继
cur.next = prev; // 2. 指向前驱
prev = cur; // 3. prev 前移
cur = next; // 4. cur 前移
}
return prev; // 新头 = 原尾
}🎯 面试要点
- 判断环形链表：快慢指针（slow 走 1 步、fast 走 2 步，相遇则有环）；找环入口：相遇后一个从头走，再次相遇即入口
- 找中点/倒数第 k 个：快慢指针（fast 先走 k 步）
- 递归版反转也常考：base case 是 head==null || head.next==null
2. 栈、队列、优先队列（堆）的核心用法？
- 栈：LIFO。用途：括号匹配、表达式求值、单调栈（见技巧页）、DFS 迭代
- 队列：FIFO。用途：BFS 层序遍历、滑动窗口
- 优先队列（堆）：取最值 O(log n)。用途：TopK、合并 K 个有序链表、贪心取最值、数据流中位数
用两个栈实现队列（经典题）
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) { in.push(x); } // 入队只进 in
private void transfer() { // in 倒进 out（一次性）
if (out.isEmpty())
while (!in.isEmpty()) out.push(in.pop());
}
public int pop() { transfer(); return out.pop(); } // 出队只从 out
public int peek() { transfer(); return out.peek(); }
}🎯 面试要点
- 均摊 O(1)：每个元素最多"进 in 一次、倒一次、出 out 一次"
- Java 中 Deque 用 ArrayDeque（比 Stack 类快，Stack 是同步的）；LinkedList 也是 Deque
- 优先队列：PriorityQueue 默认小顶堆；大顶堆用 Comparator.reverseOrder()
3. 哈希表的使用场景与手写要点？
- 核心：空间换时间——查找 O(1)。典型：两数之和（边遍历边存 map）、计数（频率）、去重、缓存（LRU）
- 冲突解决：拉链法（链表存冲突）、开放寻址（线性探测）
- 扩容：负载因子超过阈值翻倍重哈希（Java HashMap 0.75）
两数之和（一题两解）
// 暴力 O(n²)：双重循环——面试先说这个再优化
// 哈希 O(n)：一次遍历，找 target - nums[i]
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int need = target - nums[i];
if (map.containsKey(need))
return new int[]{map.get(need), i};
map.put(nums[i], i); // 边查边存，避免重复使用同一元素
}
return new int[]{};
}🎯 面试要点
- 哈希的变体：数组下标当哈希（值范围小如 26 个字母 → int[26] 替代 map，更快）
- 排序后双指针也是两数之和的经典解（有序数组）
- LinkedHashMap/哈希+链表 = LRU 的结构基础
4. 二叉树遍历与常见题型？
- 前/中/后序（递归 + 迭代都要求）；层序 BFS（队列）
- 高频题：最大深度（递归 1 行）、翻转二叉树、对称二叉树、路径总和、最近公共祖先、序列化、二叉搜索树第 k 小
最大深度 & 层序输出
// 最大深度：递归，1 行
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// 层序遍历（BFS）：每层一组
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int size = q.size(); // 关键：先记录本层节点数
List<Integer> 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;
}🎯 面试要点
- 树题 90% 是递归；递归三要素：终止条件、子问题、返回值
- BST 中序遍历 = 有序序列（第 k 小就用中序）
- 最近公共祖先（LCA）：递归判断左右子树是否含 p/q
5. 图的 DFS / BFS 模板与经典题？
图题面试考得少但高频出现：岛屿数量、课程表（拓扑排序）、腐烂橘子（多源 BFS）、克隆图。核心：visited 数组防重复访问。
岛屿数量（DFS 沉岛法，必背）
public int numIslands(char[][] grid) {
int count = 0;
for (int i = 0; i < grid.length; i++)
for (int j = 0; j < grid[0].length; j++)
if (grid[i][j] == '1') { // 发现新岛
count++;
dfs(grid, i, j); // 沉掉整座岛
}
return count;
}
private void dfs(char[][] g, int i, int j) {
if (i < 0 || j < 0 || i >= g.length || j >= g[0].length || g[i][j] != '1') return;
g[i][j] = '0'; // 原地标记 = visited
dfs(g, i+1, j); dfs(g, i-1, j);
dfs(g, i, j+1); dfs(g, i, j-1);
}🎯 面试要点
- "沉岛"技巧：访问过的格子改值，省 visited 数组
- 拓扑排序（课程表）：入度表 + BFS 队列，能弹出 n 个节点则无环
- 多源 BFS（腐烂橘子）：先把所有"源"入队，再逐层扩散