链表（LinkedList）解题总结
链表基础知识
定义
链表（Linked List）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针（Pointer）。
链表的操作
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(n) |
| 插入 | O(1)(仅插入本身，加上查找就是O(n)) |
| 删除 | O(1)(仅删除本身，加上查找就是O(n)) |
链表类型
| 链表类型 | 定义 |
|---|---|
| 单链表 | 节点只有一个指针，指向后继节点 |
| 双链表 | 节点有两个指针，一个指向前置节点，一个指向后继节点 |
| 循环链表 | 链表首尾相连 |
口诀
解题口诀：一个原则，两个考点，两个技巧，三个注意
一个原则
一个原则：画图！画图！画图！重要的事情要说三遍。链表的题目很容易把人绕晕，通过画图能够很思路理清，不容易弄错。
画图时要聚焦子结构，忽略其他信息。
两个考点
链表的题目绝大多数围绕是这两种类型：
- 指针的修改
- 链表的拼接
两个技巧
- 虚拟头：用一个虚拟头指向头节点，虚拟头就是新的头节点了，而虚拟头不是题目给的节点，不参与运算，因此不需要特殊判断
- 快慢指针：搞两个指针，一个大步走（一次走两步），一个小步走（一次走一步）
三个注意
即使画图，思路也正确了，也要注意以下三点：
- 出现了环，造成死循环
- 分不清边界，导致边界条件出错
- 搞不懂递归怎么做
解题技巧
缓存
使用数组 / map 来缓存链表中结点的信息。这种方法有点赖皮，考察链表的时候，实际上不希望使用这种方式来解决。
快慢指针
一快（一次2步）一慢（一次1步）从头节点出发。对于判断是否有环、找中间节点等问题很有效。
题目包括：
双指针
一前一后从头节点出发，或者一头一尾往中间走。对于判断倒数第N个节点、反转链表等问题特别有效。
递归
链表问题都可以分割成几个相同的子问题以缩小问题规模，再通过调用自身返回局部问题的答案从而来解决大问题的。
题目包含：
