链表

hash表

简单介绍

1. hash表可以理解为一种集合结构，在java中对应的数据结构是：HashSet和HashMap
2. 有无伴随数据是HashSet和HashMap的唯一区别，底层都是按照key依照某种实现组织的
3. CURD操作都是O(1)级别的，但相比于数据寻址的O(1)要大的多，也就是说常数更大
4. HashMap的key和value都不能是基本数据类型，如果是基本数据类型的包装类和String，数据的保存方式是深拷贝，即值传递，如果是引用数据类型就是浅拷贝，保存的都是引用地址而且占用空间统一是8个字节

有序表

简单介绍

1. 在java中的实现是：TreeSet和TreeMap
2. 相比于hash表结构，有序表是按照key通过某种排序规则进行排序的，另外hash表它是无序的，同时有序表的数据操作是O(logN)级别的
3. 如果key是引用数据类型必须提供比较器Comparator，这点同优先队列PriorityQueue
4. 由于有序的加成，除了CURD操作，有序表还有很多额外操作

额外操作

单链表和双链表

一般结构

链表类的题目如何解决

反转单链表和双链表

思路：将前一个节点存储，遍历后续节点时指向前一个节点

例题链接：

剑指 Offer 24. 反转链表 反转单链表递归解法 反转链表 II

思路，头插法：

1. 我们的目的是将[left,right]的节点反转
2. 而从left开始，我们每次反转一个
3. 准备三个指针，pre、cur、next
4. 初始化next = cur.next，然后cur.next = next.next这是为了迭代能够继续到right
5. next.next = pre.next，因为pre总是指向被反转链表的头节点，而反转一个节点A后，A就应该成为头节点
6. pre.next = next，修改pre的指向，让他指向反转链表的头节点
7. 继续循环直到循环完right-left次

注意：链表这类题目通常做法是先设置一个虚头节点，ListNode dumNode = new ListNode(-1, head)，返回链表头节点的时候，通常就返回dumNode.next

删除链表的倒数第 N 个结点

真题链接

思路：

1. 栈，先把包括虚结点在内的所有链表节点存入栈中，然后从栈中弹出n个节点，栈顶就是前驱节点了
2. 双指针，quick先走n个节点，然后同时遍历直到quick==null，slow会在倒数第n个节点的位置，不过为了方便我们应该让慢指针在第n个节点的前驱节点，然后使用pre.next = pre.next.next就可以完成节点的删除，因此可以让slow从dummy节点开始，dummy节点是我们的虚结点

合并两个有序链表

思路：

1. 按照归并排序的merge过程的模式可以顺利合并两个有序链表
2. 递归：在一次循环内只需要选出最小的节点A，然后就可以让A.next执行下次合并的结果，并且返回A

真题链接：

21. 合并两个有序链表

打印两个链表的公共部分

思路：分别遍历两个链表（前提是链表有序或者升序），相等输出，值小的向下遍历直至其中一个链表到达末尾

判断链表是否是回文结构

思路：对于这类链表的题目，我们往往会加一个虚节点插入到头节点之前，这样就能够避免链表长度的检查，也会少很多边界条件的判断（当然这是经验得出的，具体需要自己在实践中验证）

1. （这种方法没必要设置虚结点）第一次遍历，将链表元素存入栈中，第二次遍历：栈中弹出一个遍历一个，如果栈最终为空返回true，如果某次比较不等返回false
2. （设置虚结点后）快慢指针同时从虚结点开始找中间节点，其中慢指针每次走一步，快指针每次走两步，当pQ.next == null || pQ.next.next != null(pQ指的是快指针)将慢指针（不包括慢指针）后面的元素存入栈中，重复1的弹出比较操作

如上图的这种解法它没有设置虚结点，一次快慢指针起点不同，慢指针从head.next开始，快指针从head开始，而且在慢指针后面的节点入栈时包括慢指针本身

1. （设置虚结点感觉要方便很多，因为不用多设置变量）同样找中间节点，慢指针指向null，快指针后面的元素反转，然后用指针保存开始和结尾的位置，向中间遍历，进行比较操作

例题链接：

234. 回文链表

将单向链表划分成左边小、中间相等、右边大的形式

思路：

1. 将链表节点遍历放入数组、对数组进行partition操作，最后连起来
   
2. 准备6个指针，小于区域头指针和尾指针两个、等于区域头指针和尾指针两个、大于区域头指针和尾指针两个，如果小于pivot，且是第一个，头指针尾指针都指向它，如果不是，尾指针指向新的，头指针指向尾指针，其余区域同；然后小于区域的尾指针指向等于区域的头指针，等于区域的尾指针指向大于区域的头指针，像下面这样

然后判断某个区域是否为空（即没有节点），像下面这样操作：

复制含有随机指针节点的链表

思路：

1. 第一种方法：

最后返回首节点，code实现：

1. 第二种方法：

当然还要将新节点的next节点连好，然后从新老链表中分离出来

两个单链表相交的一系列问题

有环链表的特点：

有环链表的遍历会陷入循环、无环遍历会走到null

思路：

（一）判断是否有环并返回入环节点否者返回null：

1. 利用set集合，遍历链表，当某个节点在集合中存在时，它就是入环节点
2. 快慢指针：如果有环快慢指针会相遇，否则快指针先到达null，如果FN代表快指针那么（FN.next == null || FN.next.next == null 表示无环），第一次相遇时，快指针回到起点（header），此时快慢指针都走一步最后会在入环节点相遇，code如下：

注意：快慢指针必须从同一起点出发，否则最后是无法相遇的

（二）如果都无环，那么结构一定是下面这样的：

所以它们的末尾节点一定是相等的，另外长链表的长度减去短链表长度的差值，让长链表向遍历差值的距离，然后长短链表一起遍历最后会在第一个相交节点处相遇

（三）如果一个有环一个无环那么不可能相交

（四）如果都有环

1. 那么可能是下面的结构：

这种情况下先求出入环节点，如果入环节点相同就是这种情况，然后求出两条链表到入环节点的长度然后求出长度差值，让长链表向遍历差值的距离，然后长短链表一起遍历最后会在第一个相交节点处相遇

1. 也有可能是下面的结构：

如果入环节点不相同就是这种情况，那么如果从A开始遍历直到回到A节点之前，如果遇到B节点那么两条链表有相交点返回A（也可以返回B，此时A，B都算第一个相交点），如果没有遇到那么没有相交点

真题链接：

142. 环形链表 II

141. 环形链表

160. 相交链表

思路：

1. HashSet
2. 双指针，分别从两个链表触发，当任意一个为null时，该指针指向原先不同的链表，最终会使得两个指针到链表的末尾距离相等

总结

1. 链表这种题目往往都有迭代和递归两种解法，对于递归我们要记住，链表的长度尽量不要超过5000，超过5000极易造成堆栈溢出
2. 解决链表这种题目我们往往设置一个虚结点dummy，有了虚结点就能减少对head头节点的判断，最终我们只要返回dummy.next就行了
3. 链表的常用的节省空间的办法是快慢指针，通常需要调整快慢指针的距离