1.链表基础
链表是通过指针串联在一起的线性结构，
每个节点由两部分组成：
- 数据域
- 指针域（存放指向下一个节点的指针）
（最后一个节点的指针指向null）
（链表入口节点称为head，即节点）
单链表
1.1链表类型
- 单链表（如上）
- 双链表
不同于单链表，每个节点由三个部分组成，因为指针域有两个，一个指向前一个指向后。
所以双链表即可以向前查询又可以向后查询。
双链表
- 循环链表
就是单链表但是把首尾相连了
1.2链表存储方式
数组在内存是连续分布的，但是链表不是，链表是通过指针域的指针链接内存的各个节点。
1.3链表定义（JS版本）
法1
class ListNode{
val;
next = null;
constructor(value){
this.val = value;
this.next = null;
}
}
这一种默认next是null
法2
class ListNode{
constructor(value,next){
this.val = value;
this.next = next;
}
}
1.4 链表的操作
-
删除节点
删除节点
要删D，只要C的指针指向下一个就行了。
-
添加节点
添加节点
要在C和D之间添加F，要把C和D的联系切掉，所以C指向F，F指向D
1.5性能分析
性能比较
- 链表增删的时间复杂度O1是默认你知道前一个节点的指针的。
- 数组查询只用O1是因为地址是连续的，所以如果找某一个是用计算的方式比如0X0000+4+4这样，而不是从头遍历的
- 对C语言数组一开始大小要定义好，但是JS是动态数组，长度可变。
- 链表任何语言都是长度可变的
2 203移除链表元素
该题目里给出的head=[1,2,3,4,5,6]只是一个简写的形式，并不是一个数组，这个简写里面每个元素都是一个listNode，这里他的listNode已经给定义好了，我们就不需要定义了，
删除链表元素有两种方法：
1.直接使用原链表删除（会多一步判断是不是第一个元素的问题，因为第一个元素前面没有节点，想删除的方法就是把head指向下一个元素）
2.新建一个虚拟头节点dummy node，这样不论哪个位置的删除逻辑就都一样了。
2.1tips
- currNode要比较value的话别忘了是.val和val比，不是.next和val比，习惯性的写错成
while(currNode.next === val)
-
为什么建了一个新的虚拟头节点还要弄一个currNode呢？
因为这个虚拟头节点就是牵头用的，用来返回结果，真正对整个链表操作的是currNode,他们一开始都指向同一个head，但是curr一直往后动来修改整个链表。可以想象成双指针，只不过有一个指针不动弹。
并且要返回的是dummyNode的.next，因为这是我们虚构的头指针，目的只是为了让本来的head被当作第二位从而能不用分别处理
3 707.设计链表
4. 206反转链表
没什么好说的，就是双指针，因为listcode定义基本都是单链表，我们可以定义准确来说是三个指针，一个cur，一个pre，一个temp
4.1 tips
- 操作思路：
先排除掉单个和空的情况，用的!head和!head.next，能进来的情况就是head =null的时候!head才是true
然后在循环的操作里的逻辑：- 先把cur.next存到temp，不然一取消就没了，
2.把cur.next替换成pre
3.先把pre往前移到cur
4.再把cur移到temp
- 先把cur.next存到temp，不然一取消就没了，
- 最后return的是pre，因为head已经是最后的节点了，cur是null了
