目录
1 哈希表的简单介绍
1. 哈希表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随数据value，可以使用HashSet结构（C++中叫UnOrderedSet）
3. 如果既有key，又没有伴随数据value，可以使用HashMap结构（C++中叫UnOrderedMap）
4. 有无伴随数据，是HashMap和HashSet唯一的区别，底层的实际结构是一回事
5. 使用哈希表增（put）、删（remove）、改（put）和查（get）的操作，可以认为时间复杂度为O(1)，但是常数时间比较大
6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小
哈希表中所有的操作都是O(1)级别
2 有序表的简单介绍
1. 有序表在使用层面上可以理解为一种集合结构
2. 如果只有key，没有伴随数据value，可以使用TreeSet结构（C++中叫OrderedSet）
3. 如果既有key，又有伴随数据value，可以使用TreeMap结构（C++中叫OrderedMap）
4.有无伴随数据，是TreeMap和TreeSet唯一的区别，底层的实际结构是一回事
5. 红黑树、AVL树、size-balance-tree和跳表等都属于有序表结构，只是底层具体实现不同
6. 放入哈希表的东西，如果是基础类型，内部按值传递，内存占用就是这个东西的大小
7. 放入哈希表的东西，如果不是基础类型，内部按引用传递，内存占用是这个东西内存地址的大小
8.不管是什么底层具体实现，只要是有序表，都有以下固定的基本功能和固定的时间复杂度
有序表中所有的操作都是O(logN)级别
3 链表的节点结构
单链表的节点结构
Class Node<V>{
? ? ? ? V value;
? ? ? ? Node next;
}
由以上结构的节点依次连接起来所形成的链叫单链表结构
双链表的节点结构
Class Node<V>{
? ? ? ? V value;
? ? ? ? Node next;
? ? ? ? Node last;
}
由以上结构的节点依次连接起来所形成的链叫双链表结构。
单链表和双链表结构只需要给定一个头部节点head，就可以找到剩下的所有的节点。
4 面试时链表解题的方法论
1. 对于笔试，不用太在乎空间复杂度，一切为了时间复杂度
2. 对于面试，时间复杂度依然放在第一位，但是一定要找到空间最省的方法
重要技巧：
1. 额外数据结构记录（哈希表等）
2. 快慢指针
5 判断一个链表是否为回文结构
题目：给定一个单链表的头节点head，请判断该链表是否为回文结构
例子：1->2->1, 返回 true；1->2->2->1, 返回 true；15->6->15, 返回 true；1->2->3, 返回 false；
例子：如果链表长度为N，时间复杂度达到O(N),额外空间复杂度达到O(1)
解决思路：
方法①
将所有数据放进栈里，然后逐步弹出一一比较。
时间复杂度为（N）
方法②
将一半数据放进栈里，然后逐步弹出一一比较（难点：单链表的时候如何知道自己放了一半的数据，需要用到快慢指针，即快指针走两步，慢指针一次走一步）
6 将单向链表按某值划分成左边小、中间相等、右边大的形式
题目：给定一个单链表的头节点head，节点的值类型是整型，再给定一个整数pivot。实现一个调整链表的函数，将链表调整为左部分都是值小于pivot的节点，中间部分都是值等于pivot的节点，右边部分都是值大于pivot的节点
进阶：在实现原问题功能的基础上增加如下的要求
要求：调整后所有小于pivot的节点之间的相对顺序和调整前一样
要求：调整后所有等于pivot的节点之间的相对顺序和调整前一样
要求：调整后所有大于pivot的节点之间的相对顺序和调整前一样
要求：时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
解决方法：定义六个新指针，分别储存小于部分的头尾，等于部分的头尾，大于部分的头尾
注意：如果没有小于、等于或者大于部分的话，会导致空指针指向已有的指针，会报错，需要讨论清楚结果才可以使用。
7 复制含有随机指针节点的链表
题目：一种特殊的单链表节点类描述如下
class Node{
? ? ? ? int value;
? ? ? ? Node next;
? ? ? ? Node rand;
? ? ? ? Node(int val){
? ? ? ? ? ? ? ? value = val;
? ? ? ? }
}
rand指针是单链表节点结构中新增的指针，rand可能指向链表中的任意一个节点，也可能指向null。给定一个由Node节点类型组成的无环单链表的头节点head，请实现一个函数完成这个链表的复制，并返回复制的新链表的头节点。
要求：时间复杂度O(N),额外空间复杂度O(1)
解决方法：
①用哈希表map即可
②在每个节点后面克隆一个新节点紧跟着后面，然后成对取出进行rand指针的赋值。由于每个节点都是克隆到后面，因此1的rand指向3，1'可以用3的next指向3'。
?
8 两个单链表相交的一系列问题
题目：给定两个可能有环也可能无环的单链表，头节点head1和head2。请实现一个函数，如果两个链表相交，请返回相交的第一个节点。如果不相交，返回null
要求：如果两个链表长度之和为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
解题思路：
分步骤解题：
8.1 首先解决如何找到单链表中是否存在有环的点，如果有，请返回第一个节点。
方法①
用哈希表Set即可（每次将数据放入set之前现在set搜寻一般看是否已存在该数据）
②快慢指针
1.首先快慢指针都同时停留在开头
2. 快指针走两步，慢指针走一步
3. 如果有环，两个指针一定会在环上相遇
4. 相遇后，快指针回到开头，变成一次走一步，慢指针停在原地，继续一次走一步
5. 再次相遇的时刻，一定在第一个入环的节点处
?8.2 两个调用上面的函数， 开始讨论情况
两个链表分别调用8.1中的是否有环的函数
出现以下情况：
1. loop1 == null ， loop2 == null
则该两个链表不相交或者存在部分重合?
如何判断是否有交点
首先取链表1中的head1，end1以及长度len1
接着取链表2中的head2，end2以及长度len2（假设len1>len2 or 谁长谁变为head1）
判断end1内存地址是否等于end2
若等于，则head1走（len1-len2）+1? 步，head2走一步，则两个链表相交
2. loop1 ， loop2 一个等于null 另一个不等于null
则两个链表肯定不相交
3.?loop1 ， loop2 都不等于null
①都有环，但是不相交
②有环，共用一个环，入环点为同一个
③有环，共用一个环，入环点不是同一个
?
情况②：将入环点看作终点，然后就是两个无环链表的求交点问题
如何判断是情况①还是情况③，让loop1继续走，如果能等于loop2，则是情况③，如果不行则是情况①
情况①：两个链表没有相交点
情况③： 两个链表的第一个相交点取loop1或者loop2均可