罗罗编程学习记录
本页内容 展开查看

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 为主;复杂度标注平均/最坏/均摊口径,不确定版本行为标注待确认。