数据结构面试题精选

2025年阅读约 13 分钟面试指南 · 算法面试

算法数据结构面试

精选数据结构面试高频题目，涵盖链表、树、图、哈希表等核心数据结构，附经典题型和解题思路。

一句话总结

数据结构是算法面试的基石，核心考点：链表（反转/环检测/合并，快慢指针万能）、二叉树（遍历+深度+LCA）、图（BFS最短路径+Dijkstra+拓扑排序）、哈希表（冲突解决+LRU缓存）。每种结构掌握3-5道经典题即可应对面试。

链表

高频题型：

1. 反转链表：迭代法使用三个指针pre、cur、next，时间O(n)空间O(1)。递归法更简洁但空间O(n)。

2. 环形链表检测：快慢指针法，快指针走两步慢指针走一步，相遇则有环。找环入口：相遇后一个指针从头走，再次相遇即为入口。

3. 合并两个有序链表：双指针遍历，较小者先接入。递归写法更简洁。

4. 链表中间节点：快慢指针，快指针到尾时慢指针在中间。

二叉树

遍历方式：前序（根左右）、中序（左根右）、后序（左右根）、层序（BFS）。

高频题型：

1. 二叉树最大深度：递归 max(left, right) + 1，或层序遍历计数。

2. 翻转二叉树：递归交换左右子树。

3. 验证BST：中序遍历判断是否递增，或递归时传递上下界。

4. 最近公共祖先：递归查找，左右子树都找到则当前节点为LCA。

图

常见算法：

BFS：层序遍历，使用队列，适合求最短路径（无权图）。

DFS：深度遍历，使用栈/递归，适合连通性判断、拓扑排序。

Dijkstra：单源最短路径，贪心+优先队列，时间O((V+E)logV)。不能处理负权边。

拓扑排序：有向无环图的线性序列，Kahn算法（BFS+入度）或DFS后序逆序。

哈希表

核心思想：通过哈希函数将键映射到数组下标，实现O(1)的查找。

哈希冲突解决：
1. 链地址法：每个桶存链表/红黑树
2. 开放寻址法：线性探测、二次探测、双重哈希

面试经典：
1. 两数之和：哈希表存储已遍历元素
2. 字母异位词分组：排序后的字符串作为key
3. LRU缓存：哈希表+双向链表

实战场景

场景：反转链表（面试必写）

// 迭代法：O(n)时间 O(1)空间 public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode curr = head; while (curr != null) { ListNode next = curr.next; // 暂存下一个 curr.next = prev; // 反转指向 prev = curr; // prev前进 curr = next; // curr前进 } return prev; } // 递归法：更简洁但 O(n)空间 public ListNode reverseListRecursive(ListNode head) { if (head == null || head.next == null) return head; ListNode newHead = reverseListRecursive(head.next); head.next.next = head; // 反转 head.next = null; // 断环 return newHead; }

数据结构面试题精选

一句话总结

链表

二叉树

图

哈希表

实战场景

场景：反转链表（面试必写）

目录