02.3.1 链表
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列
这个知识域解决什么问题
链表是面试高频线性结构。本知识域围绕一条主线展开:单链表基础操作与反转 → 相交、环检测与快慢指针 → 哑节点哨兵与合并排序 → 双向链表、LRU 与跳表。链表题的核心是指针顺序与边界保护,所有结论先讲清“为什么这样改指针”,再给可运行代码与边界用例。
知识地图
单链表基础操作与反转(1)
→ 相交、环检测与快慢指针(2)
→ 哑节点哨兵与合并排序(3)
→ 双向链表、LRU 与跳表(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.3.1.1 | 单链表基础操作与反转 | 节点结构、遍历、插入删除、反转迭代/递归、环外残留、哑节点雏形、复杂度与边界 | 20 |
| 02.3.1.2 | 相交、环检测与快慢指针 | 快慢指针原理、判环、环入口与数学证明、环长、相交链表换头/长度差、哈希对照、边界用例 | 20 |
| 02.3.1.3 | 哑节点哨兵与合并排序 | 合并两链/ K 链、链表归并、分隔、两两交换、K 个一组翻转、去重、旋转、重排、模板与复杂度 | 20 |
| 02.3.1.4 | 双向链表、LRU 与跳表 | 双向链插入删除、LRU 哈希 + 双向链表、LinkedHashMap、LRU/LFU、跳表结构/增删查/复杂度/对比红黑树 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握单链表指针操作与反转,再 2 练熟快慢指针在判环、找入口、相交上的推导,3 用哑节点模板处理合并、排序与分组翻转,最后 4 理解双向链表与 LRU 设计、跳表索引结构。
自检
- [ ] 能手写迭代与递归反转链表,并说明指针保存顺序
- [ ] 能证明快慢指针判环与环入口结论,写出二次同速流程
- [ ] 能说清相交链表换头法的路程等式
- [ ] 能用哑节点 + 尾指针模板完成合并、分区与构造题
- [ ] 能手写哈希表 + 双向链表的 LRU get/put 流程
- [ ] 能解释跳表平均 O(log n) 的层数与空间口径
- [ ] 每题能报出时间、空间与口径,并列边界用例