1、链表的基础知识
链表是一种物理存储单元上非连续、非顺序的存储解构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
抽象概念：链表代表了一种唯一指向思想
链表适合用于存储一些经常增加、删除的数据
节点
。数据域
。指针域
实现方式包括地址、下标(相对地址)、引用
链状结构
。通过指针域的值形成了一个线性结构
链表不适合快速的定位数据，适合动态的插入和删除的应用场景
访问链表的时间复杂度
查找节点O(N)
插入节点O(1)
删除节点O(1)
几种经典的链表实现方式
- 传统方法(节点+指针)
- 使用数组模拟
- 指针域和数据域分离
- 利用数组存放下标进行索引
…
链表的典型应用场景
1、操作系统内的动态内存分配问题 2、LRU淘汰算法（LRU = Least Recently Used）
缓存是一种高速的数据结构
设备间存在速度差异，可以通过使用较多的数据存放在高速区域，而将使用较少的内容存放在相对低速的区域的方式，来对系统进行优化
经典面试题
链表的访问
LeetCode#141环状链表
- 思路1：使用哈希表(额外的存储区)存储已经遍历过的节点
- 思路2: 双指针做法
- 使用快慢指针 快指针一次向前2个节点 慢指针一次向前1个节点
- 有环的链表中，快指针和慢指针一定会在环中相遇
- 无环的链表中，快指针会率先访问到链表尾部 从而终结检测过程
LeetCode#142环状链表II
思路：使用快慢指针判断是否是环，如果是环，重新设置一个指针，与慢指针相遇时就是入环第一个节点
原因：假设之前慢指针走到入环第一个节点的距离为a,那么快指针已经走了2a（已经在环中了）,那么假设快指针距离慢指针x,那么就是说环的长度是a+x
而快指针一次走两，慢指针一次走一，那么需要x次才能相遇==》也就是慢指针走了x步(从入环的第一个节点走了x步),又环总长为a+x=>那么慢指针只需要再走a步就能回到入环的第一个节点处
那么怎样才能走a步呢，只需要重新设置一个指针ptr，每次走一步，因为慢指针也是走一步，那么等走了a次走，两个节点相遇，即此时ptr节点的位置就是入环的第一个节点
LeetCode#202快乐数
思路：转换为判断链表是否有环的问题
- 收敛性的证明
- 32位int的表示正整数大概是21亿(2^31-1)
在这个范围内 各位数字平方和最大的数是1999999999和为(9^2 * 9 + 1)730
根据鸽巢原理(pigeonhole’s principle,也译作抽屉原理)在730次循环后必定会出现重复
抽屉原理的一般含义为：“如果每个抽屉代表一个集合，每一个苹果就可以代表一个元素，假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素。” 抽屉原理有时也被称为鸽巢原理。
- 32位int的表示正整数大概是21亿(2^31-1)
链表的反转
leetCode#206反转链表
思路1：迭代反转:可以使用虚拟头节点来进行头插法
思路2：递归反转(一次拆掉一个节点并递归处理剩余的子链表)
LeetCode#92反转链表II
技巧：使用虚拟头节点(dummy head)
通常用于链表的首地址有可能改变的情况
LeetCode#25K个一组反转链表
思路：基于reverseN(反转前N个节点的链表),和新建一个reverse函数(用来判断是否够需要反转的n的节点,如果不够则返回原来的链表)
LeetCode#61旋转链表
思路:把整个链表首页相接，向后走k位后将环拆开
LeetCode#24两两交换链表中的节点
思路与LeetCode#25完全一致，是k=2的简单情形
链表的节点删除
LeetCode#19删除链表的倒数第N个节点
思路：找到前一个节点 删除后调整指针
LeetCode#83删除排序链表中的重复节点
LeetCode#82删除排序链表中的重复节点II