数据结构与算法之美 - 学习笔记
链表（Linked list）
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接次序实现的
常见缓存淘汰策略有三种：
缓存大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？就需要缓存淘汰策略决定
- 先进先出 FIFO（first in，first out）
- 最少使用策略 LFU（least frequently used）
- 最近最少使用策略 LRU（least recently used）
而链表的经典应用场景，便是 LRU 缓存淘汰算法
与数组的区别
相比数组，链表是稍微复杂一点的数据结构。
从底层存储结构来看：
数组需要一块连续的内存空间来存储，对内存的要求比较高。可能出现的问题就是：内存总的剩余空间足够，但是申请容量较大的数组时申请失败;
链表恰恰相反，它不需要一块连续的内存空间，通过‘指针’将一组零散的内存块串联起来使用。与数组不同，只要内存剩余空间足够，无论是否连续，用链表来申请空间一定会成功。但它的内存空间比数组大了将近一倍，因为链表中的每个结点不仅要存储数据，还要存储地址。
从使用场景来看：
链表适合插入、删除，时间复杂度为 O(1);
数组适合查找，支持随机访问，根据下标随机访问的时间复杂度为 O(1)。
常见的链表结构：单链表、双链表、循环链表
单链表
单链表中的每个结点都必须具备两个功能：存储数据，记录下一个结点的地址
把第一个结点叫做头结点，最后一个结点叫做尾结点
尾结点的特点:尾结点的后续指针 next 指向的不再是下一个结点。而是指向一个空地址 null
这样做的好处是：防止尾结点的后续指针 next 成为一个野指针，导致遍历停不下来，或者出现一堆本不属于该链表的垃圾数据等
循环链表
循环链表是一种特殊的单链表
单链表的尾结点指针指向 null，循环链表的尾结点指针指向头结点。所以循环链表也叫做单循环链表
当要处理的数据具有循环结构特点时，就特别适合采用循环链表。如，约瑟夫问题/丢手绢问题：N 个人围成一个圈，从第一个开始报数，第 M 个将被杀掉，最后剩下一人，其余都被杀掉
双向链表
与单链表的区别：单链表的结点只有两个域，数据域、存储后续结点的指针域。双向链表有三个域，数据域、存储后续结点的指针域（next）、存储前驱结点地址的指针域（prev）
结构上来看，双向链表支持 O(1)时间复杂度的情况下找到前驱结点，正是这样的特点，双向链表在某些情况下的插入、删除等操作都比单链表简单、高效
用空间换时间的设计思想
当内存空间充足的时候，如果更加追求代码的执行速度，可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，就要用时间换空间的设计思路
写出正确链表代码技巧
理解指针或引用的含义
将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针（指针存储的是变量的内存地址）
警惕指针丢失和内存泄露
内存泄露：
申请内存空间进行使用，用完之后忘记归还，并且申请的那块内存空间自己也访问不了（可能是将地址弄丢了），而系统也没办法把他分给需要的程序
内存溢出：
1.要求分配的内存超出系统能够给与的，系统不能满足，于是产生溢出。
2.申请 int 大小的内存，但存放 long 大小的数据，导致内存不够用，也会产生内存溢出
示例：在ab结点之间插入x
p->next = x; // 将p的next指针指向x结点；
x->next = p->next; // 将x的结点的next指针指向b结点；
p->next 指针在完成第一步操作之后，已经不再指向结点 b 了，而是指向结点 x。第 2 行代码相当于将 x 赋值给 x->next，自己指向自己。因此，整个链表也就断成了两半，从结点 b 往后的所有结点都无法访问到了
在插入结点时，要注意操作顺序。防止丢失指针，导致内存泄露。示例代码顺序颠倒即正确
利用哨兵简化实现难度
如果我们引入哨兵结点，在任何时候，不管链表是不是空，head 指针都会一直指向这个哨兵结点。我们也把这种有哨兵结点的链表叫带头链表。相反，没有哨兵结点的链表就叫作不带头链表
哨兵结点是不存储数据的。因为哨兵结点一直存在，所以插入第一个结点和插入其他结点，删除最后一个结点和删除其他结点，都可以统一为相同的代码实现逻辑了
重点留意边界条件处理
判断链表代码是否正确的边界条件：
- 链表为空，代码是否正常工作
- 链表只包含一个结点，代码是否正常工作
- 只包含两个结点，代码是否正常工作
- 代码逻辑在处理头结点和尾结点的时候，能否正常工作
举例画图，赋值思考
多写多练，没有捷径
五个常见的链表操作
序号对应 Leetcode 上题序
- 单链表反转 206
- 链表中环的检测 141
- 两个有序的链表合并 21
- 删除链表倒数第 n 个结点 19
- 求链表的中间结点 876
这里简述一下我的解题方式，具体代码实现移步下篇
单链表反转：
创建三个指针，prev 指向前一个结点（反转链表头）、cur 当前待反转结点、next 待反转下一个结点，主要作用为存储指针，避免造成内存泄露
遍历链表，next 存储下一个结点、更改 cur 指针指向、更改前结点、更新当前待反转结点
链表中环的检测：
遍历链表，给每个结点做标记，当标记结点在下一次出现，则有环
两个有序的链表合并：
创建两个指针，新链表（存储合并链表），不断比较两个排序链表头结点，将较小结点放入合并链表中，移动被放入结点的链表指针
当两个链表中指针存在指向 null 时，将另一个链表接到排列完成的链表之后，排列结束
删除链表倒数第 n 个结点
创建两个指针，快指针走 n+1 步后，慢指针开始走，直至快指针走到底
此时，慢指针位置为倒数第 n+1 个结点，操作这个结点的 next 指向下下个结点
求链表的中间结点
创建两个指针，快指针每次走两步，慢指针每次走一步，当快指针走到底时，慢指针位置为中间结点位置
