数据结构与算法（链表）
1，链表的数据结构
（1）基本实现（组成）：由一个一个结点构成。
自己动手实现：定义了一个含有数据域 和 指针的 结点类。
（2）链表主要的功能（增删改查）：定义一些接口方法
（3）过程中进行重构链表，将 增删改查 或者一些通用的接口或者属性封装到外部抽象类或者接口（方便设计给其他类用这样子）：
（整个版本一的链表过程如此）
过程中增删改查实现的具体代码就 略。。。
● 增加：可以在任意一个位置进行增加结点
● 删除：可以在任意一个位置进行删除结点
● 修改：可以在任意一个位置进行修改结点
● 查找：可以查找任意一个位置的结点
✿ 升级版本
① 拥有虚拟头结点的链表（统一了增加、删除时接口里的一些条件的判断）
② 双端（双指针）链表（加快了查找某个位置的结点~ 之前只能从头到尾的遍历，现在多了一个指针，便可以从尾到头遍历啦）
~~JDK1.8中的LinkedList中就是双向链表（从源码分析得知的）
③ 循环链表（让最后一个结点的指针指向了第一个结点）
④ 双端循环链表（有两个指针+ （最后一个结点的指针last 指向了第一个结点 、第一个结点的prev 指针指向最后一个结点））
2，链表的力扣算法题：
总结一些小套路吧 （没有通用的套路，就讲一下方法哈）：
✿ 自己需要先知道的是链表的特点就是一个一个结点构成（一般没有特别强调的链表都是普通的链表（只有一个next 指针）：找结点都是只能从头到尾去遍历找它）
（1）138_复制带随机指针的链表 的方法 ：
方法一：使用递归+ hashMap (因为随机指针：一个节点可能被多个其他节点指向)
/** hashMpa 避免重复创建 **/
当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。
方法二：间隔插秧法啦（把秧苗插进来后，以前是走一步，现在多了一个结点要多走一步）
* 第一步：插入苗
* 第二步：先处理随机指针的复制（原本有随机、next的复制都需要处理？）：优先处理随机（之所以要把苗插入，就是为了实现在同一流水线具有同一规则，如果先处理next 导致已经变成两条链表了，拿不到随机了）
（2）141_环形链表 的方法与套路 ：
方法一：使用 HashSet 实现不重复的添加 【Set 集合特点：不重复】
// HashSet 底层是HashMap（添加元素时会判断是否已经存在,已经存在会添加不成功）
if (!visited.add(head)) {
return true;
}
套路一：快慢指针法 （生活常识：操场跑圈，跑得快的最终会追上跑得慢的）
（3）142_环形链表II 的方法与套路 ：
方法一：【Set 集合特点：不重复】，通过 contains() 方法进行判断
套路一：快慢指针法 [ 追上之后，通过将特殊位置点（起点、 交点、相遇点）~ 快慢指针之间的位移差距是两倍--> 推导出起点到交点 = 相遇点到交点]
（4）160_相交链表 的方法与套路 ：
方法一：Set集合（装入一条链表，然后以它为标准，依次拿另外一条链表的每个结点与它对比）
套路一：处理一下长度，使得两条链表的长度相同后进行同步运动（相遇了即是交点）
（5）19_删除链表的倒数第N个结点 的方法与套路 ：
方法一：通过求总长len - N + 1 得到需要删除链表的前一个结点
套路一：倒序~联系到栈（后进先出~倒序思维）：通过栈（后进先出（pop掉 后面 第N个，从而可以拿到待删除结点的前一个结点））
套路二：本质上是将倒数转化成（两个点之间）具体的距离，通过设置两个距离是n 的指针（不断的往后走，走到最后，差距便是倒数）~ 数据-->距离
（6）2_两数相加 的套路 ：
套路一 ：官网用 || 把链表是否为空的所有情况都考虑（加上利用题意：将空链的数据初始为 0， 过程是将两条链的数据进行相加）
套路框架：
| while (l1 != null || l2 != null){ if (l1 != null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } |
（7）203_移除链表元素 的方法和套路 ：
方法一：递归，在从第二个结点开始进行移除，最后考虑上第一个结点的情况
套路一：加上了一个虚拟头结点后，拿自身结点的next 去 比较，一旦next 是待删除目标结点，则自身便是那个待删除结点的前一个结点
（8）206_反转链表 的方法 ：
方法一：递归
方法二：头插法
（9）21_合并两个有序链表 的方法 和 套路 ：
方法一：递归（将第一条链表从第二个结点开始与 第二条链表进行比较，然后再处理第一条链表剩下的第一个结点的情况）
套路一：两条链同时进行比较大小， 当其中一条链表数据到达了null，再处理剩下另外一条链表的数据
套路二：（6）官网用 || 把链表是否为空的所有情况都考虑（加上利用题意：将空链的数据初始为 0 ）
（10）23_合并K个升序链表 的方法 和 套路：
方法一：暴力法（一条一条添加进来的合并法）
套路一：分治合并法 （将 k 条不断地进行划分成两部分，直到 部分中的链表数量为 1，开始二合一）
套路二：优先队列法（就是小根堆（具体代码就是 PriorityQueue类(长度，比较器)）~从小到大排序：
每条链表会依据链表头的大小顺序进行排序~ 链表头小的放入前面，大的放到后面（从小到大~ 内部自动排序哈哈哈）），
每次都弹出链表头最小的链表（然后取走链表头，又放回剩余的链表（让它根据剩余链表的头在queue 中进行排序））。
（11）24_两两交换链表中的节点（这题不错） 的方法 和 套路：