算法与数据结构（一）：复杂度分析与线性结构
导语：算法面试的第一步是能把「复杂度」说清楚，之后才是结构与套路。本篇覆盖复杂度分析方法（含均摊复杂度这一易错点），以及数组、链表、栈、队列四大线性结构，所有实现均给出可运行的 Java 代码。共 15 题。
一、复杂度分析
1. 什么是时间复杂度？大 O 表示法怎么算？
答： 时间复杂度描述算法执行时间随数据规模 n 增长的趋势，大 O 表示的是渐进上界（面试默认按最坏情况分析）。
四条计算规则：
- 只保留最高阶项：
O(n² + n)→O(n²)； - 忽略常数系数：
O(2n)→O(n)、O(n/2)→O(n)； - 加法取最大：
O(f) + O(g)→O(max(f, g))（顺序执行的两段代码）； - 乘法相乘：
O(f) × O(g)（嵌套循环、外层循环内调用一个复杂度为 g 的函数）。
常见量级从小到大：
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)典型代码模式对照：
| 代码模式 | 复杂度 |
|---|---|
一次赋值、arr[i] 随机访问 | O(1) |
| 二分查找、平衡树查找 | O(log n) |
| 单层遍历、双指针、滑动窗口 | O(n) |
| 排序（快排/归并/堆排）、分治 | O(n log n) |
| 双重循环、冒泡/插入/选择排序 | O(n²) |
| 递归求子集、暴力枚举所有组合 | O(2ⁿ) |
易错点：
O(log n)的底数不影响量级（log₂n、log₁₀n只差常数倍）——所以二分查找、平衡树的高度都写O(log n)，不写O(log₂ n)。
2. 什么是空间复杂度？时间与空间如何取舍？
答： 空间复杂度衡量算法运行所需的额外存储空间随 n 的增长趋势，不含输入本身占用的空间。
O(1)：只用若干临时变量（如冒泡、插入、选择、堆排序、迭代版链表反转）；O(n)：需要与输入等规模的额外空间（如归并排序的辅助数组、哈希表去重）；O(log n) ~ O(n)：递归栈深度（如快排最坏退化时递归深度为 n）。
时间与空间的取舍原则：
| 策略 | 代价 | 收益 | 例子 |
|---|---|---|---|
| 空间换时间 | 多占内存 | 降低时间 | 哈希表替代线性查找；前缀和预计算；缓存/DP 备忘录 |
| 时间换空间 | 多算几遍 | 省内存 | 原地排序；不用 DP 表而用滚动数组 |
面试话术：不要只说"我用哈希表优化到 O(n)"，要补一句"代价是额外 O(n) 空间"。主动说出权衡，比只报复杂度更显专业。现代工程实践中通常优先时间（内存相对便宜），但在嵌入式、海量数据流场景需反过来。
3. 什么是均摊复杂度？
答： 均摊复杂度（Amortized Complexity） 指：单次操作偶尔很贵，但这些昂贵操作被大量廉价操作摊薄后，平均到每次操作的代价仍然很低。
经典例子：动态数组（ArrayList）的扩容
- 每次
add到末尾：若未满，直接写入 →O(1)； - 若已满：需要扩容并拷贝整个数组 →
O(n)； - 但扩容只在容量翻倍时才发生：从容量 1 翻倍到 n 的过程中，总拷贝次数为
1 + 2 + 4 + ... + n/2 < n，即n次add的总代价是 O(n)，均摊到每次就是O(1)。
关键区分：均摊复杂度 ≠ 平均复杂度。均摊是"最坏情况下的序列总代价"摊分，有数学保证；平均复杂度依赖输入的概率分布假设。
同类思想：并查集的路径压缩（单次可能走很长，但均摊接近
O(1)）、单调栈/单调队列（每个元素最多进出栈一次，故整体O(n)）。
二、数组
4. 数组为什么能 O(1) 随机访问？下标为什么从 0 开始？
答： 数组的 O(1) 随机访问依赖两个前提：
- 内存连续：所有元素在内存中占据连续的一段空间；
- 元素等长：同类型元素占用字节数相同。
于是第 i 个元素的地址可以直接由公式算出，一次乘加运算即可定位：
address(a[i]) = base_address + i × element_size为什么下标从 0 开始：如果从 1 开始，公式就要改成 base + (i - 1) × size，每次访问多一次减法。用 0 作为起点可以让公式最简，且 i 恰好等于偏移量。这是设计上的取舍，不是"习惯问题"。
对比：链表的第
i个节点地址无法通过计算得到（节点分散在堆中），只能从头指针顺着next一个个找，因此随机访问是O(n)。
5. 数组与链表的区别？如何选型？
答：
| 维度 | 数组 | 链表 |
|---|---|---|
| 内存布局 | 连续 | 离散（节点通过指针相连） |
| 随机访问 | O(1) | O(n) |
| 头部/中间插入删除 | O(n)（需搬移后续元素） | O(1)（改指针） |
| 尾部插入 | 均摊 O(1)（可能扩容） | O(1)（有尾指针时） |
| 额外空间 | 无（但可能有预留容量） | 每节点额外存指针 |
| 缓存友好度 | 高（顺序访问命中 CPU 缓存行） | 低（指针跳转导致缓存不命中） |
选型：随机访问/遍历多用数组（ArrayList）；频繁头部/中间增删用链表（LinkedList）。
常见误区（高频陷阱）：说"链表插入删除是
O(1)"时，必须补上前提——已持有目标节点（及前驱）的引用。如果只是"删除值为 x 的节点"，你得先遍历找到它，这一步就是
O(n)，整体仍是O(n)。这一点常被面试官用来筛人：
- 单链表删除给定节点：若只给该节点引用，可用"复制后继的值再删除后继"的技巧做到
O(1)（但无法处理尾节点）；- 知道前驱时才是真正的
O(1)——这也是双向链表的优势场景。
三、链表
6. 单链表、双向链表、循环链表的区别？
答：
| 类型 | 结构 | 优点 | 缺点 | 应用 |
|---|---|---|---|---|
| 单链表 | val + next | 结构最简单、省空间 | 只能单向遍历，删除需前驱 | 简单队列、链式栈 |
| 双向链表 | prev + val + next | 可双向遍历、O(1) 删除给定节点 | 每节点多一个指针、操作繁琐 | LinkedList、LRU 缓存 |
| 循环链表 | 尾节点 next 指回头节点 | 可从任意位置遍历整圈、无边界判断 | 易写死循环，需谨慎终止条件 | 约瑟夫环、轮询调度 |
哨兵节点（dummy head）技巧：在头节点前加一个虚拟节点，可以把"删除头节点""空链表插入"等边界情况统一化，显著减少
if判断——LRU 缓存、合并有序链表都靠它简化代码。
7. 如何反转单链表？（迭代 + 递归）
答： 反转的本质是把每个节点的 next 指针反向。两种写法：
迭代法（推荐，空间 O(1)）：
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public ListNode reverseList(ListNode head) {
ListNode prev = null; // 已反转部分的头
ListNode cur = head; // 待处理节点
while (cur != null) {
ListNode next = cur.next; // 1. 先保存后继（否则断链后找不到）
cur.next = prev; // 2. 反转指针方向
prev = cur; // 3. prev 前进
cur = next; // 4. cur 前进
}
return prev; // 循环结束时 prev 指向新头节点
}递归法（空间 O(n)，栈深度）：
public ListNode reverseList(ListNode head) {
// 递归终止：空链表或只剩一个节点
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next); // 1. 先反转 head 之后的链表
head.next.next = head; // 2. 让后继反过来指向自己
head.next = null; // 3. 断开原方向，防止成环
return newHead; // 4. 新头始终是原链表尾节点
}易错点：递归法中
head.next = null不能漏，否则原头节点与第二个节点会互相指向形成环。
8. 如何判断链表有环并找到环的入口？（Floyd 判圈算法）
答： 用快慢指针（Floyd 判圈算法，又称龟兔赛跑）：
- 判环：
slow每次走 1 步，fast每次走 2 步。若无环，fast会先到null；若有环，fast必在环内追上slow（相对速度 1，必定相遇）。 - 找入口：相遇后，让一个指针从头节点出发、另一个从相遇点出发，同速前进，再次相遇的位置就是环的入口。
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) { // 相遇 => 有环
ListNode p = head;
while (p != slow) { // 一个从头、一个从相遇点，同速走
p = p.next;
slow = slow.next;
}
return p; // 相遇处即环入口
}
}
return null; // fast 走到 null => 无环
}为什么第二次相遇就是入口？ 设：头到入口距离为 a，入口到相遇点距离为 b，相遇点绕回入口距离为 c（环长 b + c）。
slow走了a + b；fast走了a + b + k(b + c)（多绕了 k 圈）；- 由
fast = 2 × slow得：a + b + k(b + c) = 2(a + b)，化简得：
a = (k - 1)(b + c) + c即「从头出发走到入口的距离 a」等于「从相遇点绕 k-1 整圈后再走 c 到入口」。因此两指针同速前进必然在入口相遇。
复杂度：时间
O(n)、空间O(1)。变体追问："如何求环的长度？"——相遇后让一个指针绕一圈回到相遇点，步数即环长。
9. 快慢指针还能解决哪些链表问题？
答： 快慢指针是链表的"万能套路"，常见三类：
1）找中间节点（快指针走 2 步、慢指针走 1 步，快指针到头时慢指针恰在中点）：
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // 偶数个节点时返回中间偏右的那个
}2）删除倒数第 N 个节点（快指针先走 N 步，再与慢指针同步走，慢指针停在待删节点的前驱）：
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0); // 哨兵，统一"删除头节点"的边界
dummy.next = head;
ListNode slow = dummy, fast = dummy;
for (int i = 0; i < n; i++) fast = fast.next; // 快指针先走 n 步
while (fast.next != null) { // 一起走，直到快指针到尾
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next; // slow 是待删节点的前驱
return dummy.next;
}3）合并两个有序链表（双指针比较，配合哨兵节点）：
public ListNode mergeTwoLists(ListNode a, ListNode b) {
ListNode dummy = new ListNode(0), cur = dummy;
while (a != null && b != null) {
if (a.val <= b.val) { cur.next = a; a = a.next; } // <= 保证稳定性
else { cur.next = b; b = b.next; }
cur = cur.next;
}
cur.next = (a != null) ? a : b; // 接上剩余部分
return dummy.next;
}延伸：链表排序最优解是归并排序（
O(n log n)、空间O(log n)递归栈），因为链表无法随机访问，快排的 partition 在这里并不占优。
10. 如何用哈希表 + 双向链表实现 LRU 缓存？
答： LRU（Least Recently Used）要求 get 和 put 都是 O(1)，因此必须"查找快 + 增删快"：
- 哈希表负责
O(1)定位节点； - 双向链表负责
O(1)删除/移动节点（单向链表删给定节点还需前驱，做不到O(1)）； - 用两个哨兵节点（
head/tail）简化边界：head.next是最新的、tail.prev是最旧的。
import java.util.HashMap;
import java.util.Map;
class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // 哨兵：head.next = 最新
private final Node tail = new Node(0, 0); // 哨兵：tail.prev = 最旧
private static class Node {
int key, value;
Node prev, next;
Node(int k, int v) { key = k; value = v; }
}
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
moveToHead(node); // 访问后提升为"最新"
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) { // 已存在：更新值并提升
node.value = value;
moveToHead(node);
return;
}
if (map.size() == capacity) { // 容量满：淘汰最久未使用
Node oldest = tail.prev;
remove(oldest);
map.remove(oldest.key); // 注意：要从 map 中一并删除
}
Node newNode = new Node(key, value);
map.put(key, newNode);
addToHead(newNode);
}
private void moveToHead(Node node) {
remove(node);
addToHead(node);
}
private void addToHead(Node node) { // 头插
node.next = head.next;
node.prev = head;
head.next.prev = node;
head.next = node;
}
private void remove(Node node) { // 双向链表 O(1) 摘除
node.prev.next = node.next;
node.next.prev = node.prev;
}
}三个易错点：①
Node里必须存 key，否则淘汰时要反查 key 才能从 map 删除（变成O(n)）；② 淘汰时要同时从链表和 map 中移除；③ 用哨兵节点可避免头尾指针为null的大量判空。延伸：LFU（按访问频率淘汰）需要额外维护频率桶，通常用"频率 → 双向链表"的
HashMap组合实现，思路比 LRU 复杂一档。
四、栈与队列
11. 栈和队列的区别？栈有哪几种实现？
答： 栈是 LIFO（后进先出），队列是 FIFO（先进先出）。
栈的三种 Java 实现：
| 实现 | 说明 | 推荐度 |
|---|---|---|
ArrayDeque | 数组实现的双端队列，非线程安全、无同步开销 | ⭐ 首选 |
链表实现（LinkedList） | 不受容量限制，但每节点有指针开销 | 备选 |
Stack 类 | 继承自 Vector，方法带 synchronized；且暴露了 get(i) 等向量方法，破坏栈语义 | 不推荐 |
// 推荐写法：Deque 的 push/pop/peek 即栈语义
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
int top = stack.pop(); // 2为什么
Stack被淘汰：① 继承Vector导致粗粒度同步、性能差；②Stack继承了Vector的全部公开方法，使用者可以按下标访问中间元素（get(1)），破坏了"只能操作栈顶"的抽象。官方文档也建议用Deque替代。
12. 如何用两个栈实现队列？
答： 用 in 栈负责入队、out 栈负责出队。关键点：只在 out 为空时，才把 in 全部倒入 out（保证顺序被反转两次，恢复 FIFO）。
class MyQueue {
private final Deque<Integer> in = new ArrayDeque<>();
private final Deque<Integer> out = new ArrayDeque<>();
public void push(int x) { in.push(x); }
public int pop() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.push(in.pop()); // 一次性倒过去
}
return out.pop();
}
public int peek() {
if (out.isEmpty()) {
while (!in.isEmpty()) out.push(in.pop());
}
return out.peek();
}
public boolean empty() { return in.isEmpty() && out.isEmpty(); }
}为什么是均摊
O(1)：每个元素在整个生命周期内最多被"倒"一次（从in到out），因此 n 次操作总代价O(n)，均摊每次O(1)。若每次pop都倒一次，就会退化成O(n)——这是本题的考点所在。
13. 什么是单调栈？如何用它解决「每日温度」？
答： 单调栈指栈内元素保持单调（递增或递减）的栈。用途是解决「找每个元素左边/右边第一个比它大（或小）的元素」这一类问题。
核心思路：遍历时若当前元素破坏了单调性，就不断弹栈并结算被弹出元素（当前元素正是它右边第一个更大/更小的元素）。
以「每日温度」（返回每天距离下一个更高温度的天数）为例：
public int[] dailyTemperatures(int[] temperatures) {
int n = temperatures.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标，栈内温度单调递减
for (int i = 0; i < n; i++) {
while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int prev = stack.pop();
res[prev] = i - prev; // 找到了更高温度，出栈并结算
}
stack.push(i);
}
return res; // 留在栈中的下标无更高温度，保持 0
}复杂度：每个元素最多入栈一次、出栈一次，故整体时间
O(n)、空间O(n)。同类应用：
接雨水（用单调递减栈求每个坑的左右边界）、柱状图中最大的矩形、下一个更大元素、股票价格跨度。看到"找下一个更大/更小"就该想到单调栈。
14. 队列有哪些类型？循环队列如何实现？
答： 常见队列类型：
| 类型 | 特点 | 应用 |
|---|---|---|
| 顺序队列（数组） | 简单，但出队后 front 前移会造成假溢出 | — |
| 循环队列 | 用取模把数组首尾相连，解决假溢出 | 环形缓冲区、生产者-消费者 |
| 链式队列 | 用链表实现，无容量上限 | 一般队列 |
| 双端队列（Deque） | 两端都可进出 | 单调队列、滑动窗口 |
| 优先队列（PriorityQueue） | 按优先级出队，底层是堆，操作 O(log n) | Top K、任务调度 |
「假溢出」：数组实现的顺序队列中，rear 到达数组末尾但数组前面还有空位，此时却无法再入队——因为 rear 不能折返。循环队列用 (index + 1) % capacity 让下标回绕即可解决。
循环队列实现（用 size 记录元素个数，从而区分"空"与"满"，避免浪费一个槽位）：
class MyCircularQueue {
private final int[] data;
private int head = 0; // 队首下标
private int size = 0; // 当前元素个数
public MyCircularQueue(int k) { data = new int[k]; }
public boolean enQueue(int value) {
if (isFull()) return false;
data[(head + size) % data.length] = value; // 取模实现环形回绕
size++;
return true;
}
public boolean deQueue() {
if (isEmpty()) return false;
head = (head + 1) % data.length; // 头指针回绕
size--;
return true;
}
public int Front() { return isEmpty() ? -1 : data[head]; }
public int Rear() {
return isEmpty() ? -1 : data[(head + size - 1) % data.length];
}
public boolean isEmpty() { return size == 0; }
public boolean isFull() { return size == data.length; }
}另一种常见写法：不额外维护
size，而是故意浪费一个槽位，用(rear + 1) % capacity == front判断队满——两种写法面试都算对，说清取舍即可。
15. 什么是单调队列？如何求滑动窗口最大值？
答： 单调队列是一个双端队列，队列内元素值保持单调递减（求最大值时），队首始终是当前窗口的最大值。
两条维护规则：
- 队首过期：若队首下标已滑出窗口（
<= i - k），从队首弹出； - 队尾淘汰：新元素入队前，把队尾所有比它小的元素弹出（它们不可能是未来窗口的最大值了）。
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
int[] res = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // 存下标，值单调递减
for (int i = 0; i < n; i++) {
// 1. 队首滑出窗口则移除
if (!dq.isEmpty() && dq.peekFirst() <= i - k) dq.pollFirst();
// 2. 队尾比当前元素小的都弹掉，维持单调递减
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
// 3. 窗口形成后，队首即为最大值
if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
}
return res;
}复杂度：每个元素最多进出队各一次，总时间
O(n)、空间O(k)，优于暴力解法的O(nk)。易混点：单调栈解决"找下一个更大元素"（关注边界）；单调队列解决"窗口内最值"（关注区间）。两者都靠"及时淘汰不可能成为答案的元素"来降低复杂度——这是同一个思想。