02.3 链表、栈与队列
所属:全栈开发面试题库 / 02 数据结构与算法
覆盖范围
- 单链表遍历、插入删除、反转、区间反转与哑节点模板
- 快慢指针:判环、环入口与数学证明、相交链表
- 链表合并、归并排序、分组翻转、去重、旋转与重排
- 双向链表、LRU 缓存设计、跳表结构与复杂度对比
- 栈语义、括号匹配、表达式求值、字符串解码与递归调用栈
- 单调栈:每日温度、下一个更大、柱状图最大矩形、接雨水
- 队列与双端队列、循环队列、两栈队列、队列实现栈、BFS 层序
- 优先队列与堆:Top-K、第 K 大、双堆中位数、单调队列窗口最值、最小栈
子主题
| 编号 | 主题 | 覆盖范围 |
|---|---|---|
| 02.3.1 | 链表 | 4 个子主题 80 题:单链表基础与反转、相交环检测与快慢指针、哑节点哨兵与合并排序、双向链表 LRU 与跳表 |
| 02.3.2 | 栈与队列、单调栈 | 4 个子主题 80 题:栈基础与表达式求值、单调栈与柱状图接雨水、队列双端队列与循环队列、优先队列堆与综合设计 |
面试题索引
| 编号 | 题目 | 难度 | 频率 | 所在页面 |
|---|---|---|---|---|
| 02.3.1.1-004 | 反转单链表迭代版(LC 206) | 简单 | ★★★★★ | 单链表基础操作与反转 |
| 02.3.1.1-007 | 反转链表区间(LC 92) | 中等 | ★★★★☆ | 单链表基础操作与反转 |
| 02.3.1.1-011 | 删除倒数第 N 个节点(LC 19) | 中等 | ★★★★★ | 单链表基础操作与反转 |
| 02.3.1.1-013 | 回文链表(LC 234) | 简单 | ★★★★☆ | 单链表基础操作与反转 |
| 02.3.1.2-002 | 判断链表是否有环(LC 141) | 简单 | ★★★★★ | 相交、环检测与快慢指针 |
| 02.3.1.2-003 | 找环入口(LC 142) | 中等 | ★★★★★ | 相交、环检测与快慢指针 |
| 02.3.1.2-007 | 相交链表(LC 160) | 简单 | ★★★★☆ | 相交、环检测与快慢指针 |
| 02.3.1.3-001 | 合并两个有序链表(LC 21) | 简单 | ★★★★★ | 哑节点哨兵与合并排序 |
| 02.3.1.3-002 | 合并 K 个有序链表(LC 23) | 困难 | ★★★★☆ | 哑节点哨兵与合并排序 |
| 02.3.1.3-004 | 排序链表(LC 148)归并 | 中等 | ★★★★☆ | 哑节点哨兵与合并排序 |
| 02.3.1.3-008 | K 个一组翻转链表(LC 25) | 困难 | ★★★★☆ | 哑节点哨兵与合并排序 |
| 02.3.1.4-006 | 手写 LRU 缓存(LC 146) | 中等 | ★★★★★ | 双向链表、LRU 与跳表 |
| 02.3.1.4-011 | 跳表是什么结构? | 高级 | ★★★☆☆ | 双向链表、LRU 与跳表 |
| 02.3.2.1-004 | 有效括号(LC 20) | 简单 | ★★★★★ | 栈基础与括号表达式求值 |
| 02.3.2.1-007 | 逆波兰表达式求值(LC 150) | 中等 | ★★★★☆ | 栈基础与括号表达式求值 |
| 02.3.2.2-007 | 柱状图中最大矩形(LC 84) | 困难 | ★★★★☆ | 单调栈与柱状图、接雨水 |
| 02.3.2.2-008 | 接雨水(LC 42)单调栈法 | 困难 | ★★★★★ | 单调栈与柱状图、接雨水 |
| 02.3.2.3-003 | 用两个栈实现队列(LC 232) | 简单 | ★★★★☆ | 队列、双端队列与循环队列 |
| 02.3.2.3-006 | 循环队列(LC 622)设计 | 中等 | ★★★★☆ | 队列、双端队列与循环队列 |
| 02.3.2.4-007 | 数组中第 K 大元素(LC 215) | 中等 | ★★★★★ | 优先队列、堆与栈队列综合 |
| 02.3.2.4-008 | 数据流中位数(LC 295)双堆 | 困难 | ★★★★☆ | 优先队列、堆与栈队列综合 |
| 02.3.2.4-009 | 滑动窗口最大值(LC 239)单调队列 | 困难 | ★★★★★ | 优先队列、堆与栈队列综合 |
| 02.3.2.4-011 | 最小栈(LC 155)设计 | 中等 | ★★★★☆ | 优先队列、堆与栈队列综合 |
当前状态
- 02.3.1 已完成 4 个子主题、80 题;02.3.2 已完成 4 个子主题、80 题,合计 160 题,全部为可学习型详解。
- 页面结构:知识域首页 + 子主题页 + 分册 TOC 三层登记。
- 代码以 Java 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。