JS 链表

链表：多个元素组成的列表
元素存储不连续，用next指针连在一起

链表

数组VS链表
数组：增删非首尾元素时往往需要移动元素。
链表：增删非首尾元素时，不需要移动元素，只需要更改next的指向即可

JS中没有链表这个数据结构。但是可以用Object模拟链表

const a = { val: 'a' };
const b = { val: 'b' };
const c = { val: 'c' };
const d = { val: 'd' };
//以上四个元素存储不连续
a.next = b
b.next = c
c.next = d
//a b c d 都可以是链表  abcd大链表 a就是链表的头部 就是一个嵌套的Object

//遍历链表 按顺序打印abcd

//首先声明一个指针p,然后循环
let p = a
while (p) { 
    console.log(p.val)
    p=p.next
}

//链表插入值,在c和d之间插入一个值

const e = { val: 'e' }
c.next = e
e.next = d

//删除 删除e
c.next = d

链表练习：

leetcode 237 删除链表中的节点

给你被要求删除的节点，你去把他删除掉。
解题思路：
常规删除节点只需要找到上一个节点，直接把他next指向被删除节点的下一个节点即可。
本题无法直接获取被删除节点的上一个节点。
如何不拿到上一个节点，还能删除这个节点呢？
和下一个节点进行交换，就是让被删除节点等于下一个节点。此时就相当于删除了下一个节点。

4 5 1 9 删除 1
1、变为4 5 9 9
2、删除最后一个9

var deleteNode = function(node) {
    node.val = node.next.val
    node.next = node.next.next
};

时间复杂度：没有任何循环所以是 o1
空间复杂度：没有数组或矩阵也是 o1

leetCode 206反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
1-2-3-4-5
变为
5-4-3-2-1

解题思路：

反转两个节点
1-2
只需要将2的next指向1即可

反转多个节点：双指针遍历链表，然后重复上述反转两个节点的操作。

单指针链表（上面学的）：指针指向1，然后指向 2 直到指向链表的结尾

双指针遍历链表：1-2
一个指针指向2 (p1)，另一个指针指向1(p2)(此时反转一下p1.next = p2)
指向2的指针，下一步指向3.p1 = p1.next
指向1的指针下一步指向2， p2 = p1;
直到靠前的指针走到链表的尽头为止。p1 === null p2 === 最后一项。
在遍历的过程中，两个节点两个节点进行反转即可成功。

解题
输入1-2-3-4-5-null
输出5-4-3-2-1-null
1、新建两个指针，双指针一前一后遍历链表
2、遍历过程中不断反转双指针，遍历结束即成功。

var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1){
       const tmn = p1.next
        p1.next = p2
        p2 = p1;
        p1 = tmn
    }
    return p2
};

时间复杂度：有一个while循环体显然复杂度o(n)
空间复杂度：我们的临时变量是单个值没有数组和矩阵，所以是o(1)

leetcode 2 两数相加

给你两个链表代表整数。逆序存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
输入：
2-4-3
5-6-4

输出 7-0-8
因为342+468=807

解题思路：
相加操作
需要遍历链表

解题步骤：
1、新建空链表（输出的新链表）
2、遍历两个相加的链表。模拟相加操作
将个位数追加到新链表，十位数留到下一位相加。

var addTwoNumbers = function(l1, l2) {
    const l3 = new ListNode(0) //新建链表节点 空节点
    let p1 = l1 //新建指针指向链表的头部
    let p2 = l2
    let p3 = l3

    let carry = 0
    while(p1||p2){//p1 或 p2 一个有值就执行循环
    //两个链表可能长短不一 所以要判断是否存在 不存在就当他是0 
        const v1 = p1? p1.val : 0
        const v2 = p2? p2.val : 0
        const val = v1 + v2 + carry
        carry = Math.floor(val/10) //当val大于9时 获取val 十位上的数，然后下一轮循环加上,如果不大于9就为空
        p3.next = new ListNode(val%10)
        if(p1) p1 = p1.next
        if(p2) p2 = p2.next
        p3 = p3.next
    }
    if(carry){ //如果最后一位相加大于10 循环已经结束了 自己加上
        p3.next = new ListNode(carry)
    }
    return l3.next //因为我们新建的链表 是在空节点的后面 不包括他自己 所以要从next开始

时间复杂度：
有while 所以时间复杂度 o(n) n为两个链表中的长度大的值。
空间复杂度：
没有数组矩阵
但是有一个新造的链表
链表的长度可能是链表中较长的一个或加一位
所以也是 o(n)n同上

LeeCode: 83. 删除排序链表中的重复元素

给定一个已排序的链表的头 head ，删除所有重复的元素，使每个元素只出现一次。返回已排序的链表。

解题思路：
输入1-1-2
输出：1-2
因为链表是有序的，所有重复元素一定相邻。，
遍历链表
如果发现当前元素和下个元素值相同，就删除下个元素

解题步骤：
1、遍历链表
如果发现当前元素和下个元素值相同，就删除下个元素
2、遍历结束后返回原链表头部

var deleteDuplicates = function(head) {
    let p = head
    while(p && p.next){ //确保p下一个元素也存在
        if(p.val === p.next.val){
            p.next = p.next.next
        }else{//前后两个不同我才变，如果相同我就不变为下一个，我就看看和下下个一样不
             p = p.next
        }     
    }
    return head
};

时间复杂度：O(n) ,因为有一个while n就是链表长度
空间复杂度：O（1）没有额外存储任何线性增长的变量。没有数组矩阵链表。

LeetCode：141. 环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

解题思路：

环

两个人在圆形操场上同时跑，速度快的人会超过速度慢的人一圈。
用一快（走两步）一慢（走一步）两个指针遍历链表，如果指针能够重逢，那么链表就有环。

解题步骤
用一快（走两步）一慢（走一步）两个指针遍历链表，如果指针能够重逢，返回true。反之false。

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p1 = head
    let p2 = head
    while(p1 && p2 && p2.next){ //都有值的情况下循环。 如果p2.next 没有值，那 p2.next.next会报错。
        p1 = p1.next
        p2 = p2.next.next
        if(p1 === p2){
            return true
        }
    }
    return false
};

时间复杂度：它有一个while循环体时间复杂度是O(n) 如果跑4 3圈。也是O(n) ,O（2n）O(n)是一个量级的。
空间复杂度：没有额外线性增长的数据结构，没有数组矩阵链表，所以说空间复杂度为O（1）。

JS中的原型链

原型链的本质是链表。

原型链上的节点是各种原型对象(JS中有各种各样内置的类，如function object string array等，所谓原型对象就是这些类的prototype值)，比如：Function.prototype Object.prototype。
原型链通过-proto-属性链接各种原型对象。（链表是通过next连接的）

obj.proto === Object.prototype
Object.prototype.proto ===null

fun.proto = Function.prototype
Function.prototype.proto === Object.prototype
Object.prototype.proto ===null

arr.proto = Array.prototype
Arrayn.prototype.proto === Object.prototype
Object.prototype.proto ===null

我们发现JS变量除了对象都是先指向自己类型的原型对象再指向Object类型的原型对象，这对于string和number等也是成立的。

知识点：
1、如果A沿着原型链能找到B.prototype，那么A instanceof B 为 ture
instanceof运算符用来判断一个构造函数的prototype属性所指向的对象是否存在另外一个要检测对象的原型链上
fun instanceof Function /true
fun instanceof Object /true
arr同理
2、如果在A对象上没有找到x属性，那么会沿着原型链找x属性

const obj = {}
const fun = ()=>{
}
Object.prototype.x = 'x'
obj.x = 'x'
fun.x = 'x'

面试题
1、简述instanceof原理，并用代码实现。
原理：如果A沿着原型链能找到B.prototype，那么A instanceof B 为 ture
遍历A的原型链，如果找到B.prototype 返回true 否则 false
先用指针遍历原型链，遍历过程中找B

const instanceOf = (A,B)=>{
  let p = A
  while(p){
    if(p === B.prototype){
      return true
    }
    p = p.__proto__
  }
  return false
}

2、

var foo = {}
var F = function(){}

Object.prototype.a = 'value a'
Function.prototype.b = 'value b'

console.log(foo.a)// 'value a'
console.log(foo.b)//undefined

console.log(F.a)// 'value a'
console.log(F.b)//'value b'

使用链表指针获取JSON节点值,这是一个前端日常工作中的一个应用

const json = {
  a:{b:{c:1}},
  d:{e:2}
}
//path是一个数组 记录了json属性的路径
const path = ['a','b','c']
//我们要求沿着这个路径最后得到的节点值是多少

let p = json
path.forEach(k=>{
  p = p[k]
})// 指向C 得到1

const path = ['a','b']
得到 {c:1}