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

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) 的层数与空间口径
  • [ ] 每题能报出时间、空间与口径,并列边界用例