链表
JavaScript是一个比较魔幻的语言，它本身是不自带linkList的数据结构的，JS中的链表是通过对象来模拟的。下面来一段示例代码
let a = {val:1}
let b = {val:3}
let c = {val:5}
let d = {val:7}
let e = {val:9}
a.next = b
b.next = c
c.next = d
d.next = e
console.log(a) // { val: 1, next: { val: 3, next: { val: 5, next: {val: 7, next: {val: 9} } } } }这样,我们通过打印a这个对象，可以看到a中有一个next属性，并且指向的是b这个对象，然后，b对象中也有val和next属性，其中指向的c对象
这样，对象a就是这个链表的head节点，
遍历一个链表怎么实现呢？
let p = head
while(p){
console.log(p.val)
p = p.next
}
这样 这个链表中的元素就会被遍历一遍，这里的p 是一个指针，它所指向的是head节点的地址，所以我们在while循环中，改变p的指向地址，就不会改变head
链表的插入
let f = {val:10}
d.next = f
f.next = e这样 链表的结构就是 a->b->c->d->f->e
链表中的删除
d.next = e将前面d和e中间连接的f直接断开连接，直接将d指向e，那么f就自己断开了
leetcode中是如何定义链表的呢，我们随便打开一题链表题，都可以看到，在代码上面的注释中，有一个函数，里面有两个参数，val和next，那么这就是链表中的基本结构。一个是当前节点的值，另外一个是指向了下一个节点。
接下来实际操作一题我自认为最简单的一链表题。83. 删除排序链表中的重复元素
这一题还是偏简单，思路：用指针遍历链表，如果当前节点的val属性和当前节点的next节点的val属性相等，就将当前节点与next的next节点连接，即删除next节点。
var deleteDuplicates = function(head) {
let p =head; // 指针p
while(p&&p.next ) { 这里也要判断p不是最后一个节点，不然它的next是一个null，那么程序就会报错
if(p.val == p.next.val) { // 判断当前节点的val属性和下一个节点的val是否相等
p.next = p.next.next // 删除next节点
}
else p = p.next //遍历这个链表
}
return head
};那么，链表的基础就说到这儿了，（更新一题，反转链表）
leetcode 206
就是反转一个链表，
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL先遍历链表 这是肯定的，然后是一步：当前节点的next节点，等于当前节点，然后当前节点等于当前节点的next节点，就拿一个最简单的 1->2来说 相当是1和2互换位置，但是这个操作不简单。前面说了，JS的链表是一个指向对象的地址，如果你直接将当前节点等于next节点的话，那么next节点也指向了一个新的地址，而不是原来的next节点，所以我们按照C语言中写一个两数交换的函数一样，需要传递的是值的指针，才可以交换，我们定义一个临时变量temp，让它等于next节点，然后让当前节点等于这个temp对象，并且让next指针指向当前节点，代码如下:
const reverseList = head => {
let p1 = head
let p2 = null
while(p1) {
const temp = p1.next
p1.next = p2
p2 = p1
p1 = temp
}
return p2
}function ListNodeToArray(head) {
let p = head
let arr = []
while(p&&p.next) {
arr.push(p.val)
p = p.next
}
arr.push(p.val)
return arr
}
let arr = ListNodeToArray(head)
function arrToListNode(arr) {
let h = new ListNode(0)
let p = h
for(let i=0;i<arr.length;i++) {
p.next = new ListNode(arr[i])
p = p.next
}
return h.next
}接下来看原型链。
这个东西带有一个链字，那么它就很可能和链表有关系
看一下下面这一张图。
原型是指一个构造函数(constructor)的属性
首先要了解两个东西
prototype和__proto__
原型链中的“链”字，指的是，一个对象从自己开始找，找父级，在找父级，这个过程叫做链。和作用域链有那么一丝丝相像，都是一级一级往上找，直到null (原型的终点) window/global （作用域的终点）
举一个简单的例子
函数的父亲是对象，那么 Function.prototype === Object.__proto__ // true
function foo() {}
let f = new foo()
f.__proto__ === foo.prototype // true（2020-9-6）明天继续
9-13 更新...
这里可以拓展到 typeof和instanceof相关知识，我们知道，数组，null和对象都会被typeof看作是对象，那么对于数组的判断不能够用typeof来，这时，就有了其他的很多方法，例如instanceof，
let arr = [1,2,3,4]
arr instanceof Array // true为什么instanceof可以获取到arr的类型呢，其实就是利用了原型链
我们可以看到 arr.__proto__ == Array.prototype // true
其实instanceof的原理就是 左边实例的__proto__ 一直向上查找，直到找到了null，如果到了null还不相等，那么就不属于这个类，否则就是它的实例
直接贴上代码，其中也有类似链表中的遍历过程
let myinstanceof = (left, right) => {
left = left.__proto__
right = right.prototype
while(true) {
if (left === null) return false
if (right === left) return true
left = left.__proto__ // 这一步操作类似链表中的遍历
// 右指针（right）不变 左指针遍历 找到null就是false 在过程中找到右指针，那么就可以
}
}其实 差不多了吧。。
