链表
与数组相似，链表也是一种线性数据结构
单链表
单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。
操作
与数组不同，无法在常量时间内访问单链表中的随机元素。如果想要获得第i个元素，必须从头结点逐个遍历。
添加操作-单链表
- 使用给定值初始化新结点
cur - 将
cur的”next”字段链接到prev的下一个结点next - 将
prev中的”next”字段链到cur
与数组不同，不需要将所有元素移动到插入元素之后。因此，非常高效。
删除操作-单链表
想从单链表中删除现有结点cur，可以分两步完成：
- 找到cur的上一个结点
prev及其下一结点next； - 接下来链接
prev到cur的下一个结点next
删除第一个结点
如果想要删除第一个结点，可以简单地将下一个结点分配给head。
双指针技巧
链表中的双指针
- 如果没有环，快指针将停在链表的末尾。
- 如果有环，快指针最终将与慢指针相遇。
环形链表
给定一个链表，判断链表中是否有环
通过使用具有不同速度的快、慢两个指针遍历链表，空间复杂度可以降低至1。慢指针每次移动一步，而快指针每次移动两步。
如果列表中不存在环，最终快指针将会最先到达尾部，此时我们可以返回false。
环形链表II
不允许修改给定的链表
用一个Set保存已经访问过的节点，可以遍历整个列表并返回第一个出现重复的节点。
算法：
首先，我们分配一个Set去保存所有的列表节点。我们逐一遍历列表，检查当前节点是否出现过，如果节点已经出现过，那么一定形成了环且它是环的入口。否则如果有其他点是环的入口，我们应该先访问到其他节点而不是这个节点。其他情况，没有成环则直接返回 null 。
算法会在遍历有限个节点后终止，这是因为输入列表会被分成两类：成环的和不成环的。一个不成欢的列表在遍历完所有节点后会到达 null - 即链表的最后一个元素后停止。一个成环列表可以想象成是一个不成环列表将最后一个null元素换成环的入口。
如果 while 循环终止，我们返回 null 因为我们已经将所有的节点遍历了一遍且没有遇到重复的节点，这种情况下，列表是不成环的。对于循环列表， while 循环永远不会停止，但在某个节点上， if 条件会被满足并导致函数的退出。
找出两个链表的交点
删除链表的倒数第N个节点
经典问题
反转链表
一种解决方案时按原始顺序迭代结点，并将它们逐个移动到列表的头部
移除链表元素
删除结点的步骤
- 找到该结点的前一个结点
- 进行删除操作
三种方式：
- 删除头结点时另作考虑（由于头结点没有前一个结点）
- 添加一个虚拟头结点，删除头结点就不用另做考虑
- 递归
奇偶链表
想法
将奇节点放在一个链表里，偶链表放到另一个链表里。然后把偶链表接在奇链表的尾部
小结
- 可以同时使用多个指针
有时，当你为链表问题设计算法时，可能需要同时跟踪多个结点。应该记住需要跟踪哪些结点，并且可以自由地使用几个不同的结点指针来同时跟踪这些结点。如果你使用多个指针，最好为它们指定适当的名称，以防将来必须调试或检查代码 - 在许多情况下，需要跟踪当前结点的前一结点
你无法追溯单链表中的前一结点。因此，你不仅要存储当前结点，还要存储前一个结点。这在双链表中是不同的。
双链表
双链表以类似的方式工作，但还有一个引用字段，称为prev字段。有了这个额外的字段，就能够知道当前结点的前一结点。
操作
可以与单链表相同的方式访问数据：
- 不能再常量级的时间
访问随机位置。 - 必须从头部遍历才能得到我们想要的第一个结点
- 在最坏的情况下，时间复杂度是
O(N)，其中N是链表的长度
添加操作-双链表
删除操作-双链表
从双链表中删除一个现有的结点cur，可以简单地将它的前一结点prev与下一个结点next链接起来。
小结-链表
- 在单链表中，它无法获取给定结点的前一结点，因此在删除给定结点之前必须花费
O(N)时间来找出前一结点 - 在双链表中，这会更容易，可以使用
prev引用字段获取前一结点。因此可以在O(1)时间内删除给定结点。