3. 链表

1. 链表简介

• 多个元素组成的列表

• 元素存储不连续，用 next 指针连在一起

  
  image.png

数组 vs 链表

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

// 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;

image.png

// * 遍历链表（重要）
let p = a;
while(p) {
    console.log(p.val);
    p = p.next;
}
// 插入
const e = { val: 'e' };
c.next = e;
e.next = d;
// 删除 e
c.next = d;

2. 算法题

image.png image.png

// 时间复杂度O(1) 空间复杂度O(1)
var deleteMode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

206. 反转链表

image.png image.png

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

image.png image.png

var addTwoNumbers = function(l1,l2) {
   var l3 = new ListNode(0);
   let p1 = l1;
   let p2 = l2;
   let p3 = l3;
   let carry  = 0;
   while(p1 || p2) {
      const v1 = p1 ? p1.val : 0;
      const v2 = p2 ? p2.val : 0;
      const val = v1+ v2 + carry;
      carry  = Math.floor(val/10);
      p3.next = new ListNode(val%10);
      if(p1) p1 = p1.next;
      if(p2) p2 = p2.next;
      p3 = p3.next;
   }
   if(carry) {
      p3.next = new ListNode(carry);
   }
   return l3.next;
}

时间复杂度O(n)
空间复杂度O(n)

image.png image.png image.png

var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next) {
       if(p.val === p.next.val) {
          p.next = p.next.next;
       } else {
          p = p.next;
       }
    }
    return head;
}

时间复杂度O(n)
空间复杂度O(1)

image.png image.png image.png

// {ListNode} head
// return {Boolean}
var hasCycle = function(head) {
    let p1 = head;
    let p2 = head;
    while(p1 && p2 && p2.next) {
       p1 = p1.next;
       p2 = p2.next.next;
      if(p1 === p2) {
           return true;
      }
    }  
    return false;
}

时间复杂度O(n)
空间复杂度O(1)

3. 前端与链表

1. 原型链简介

• 原型链的本质是链表
• 原型链上的节点是各种原型对象，比如 Function.prototype、Object.prototype......
• 原型链通过 proto 属性连接各种原型对象

2. 原型链长啥样？

• obj -> Object.prototype -> null
• func -> Function.prototype -> Object.prototype -> null
• arr-> Array.prototype -> Object.prototype -> null

3. 原型链知识点

• 如果 A 沿着原型链能找到 B.prototype，那么 A instanceof B 为 true
• 如果 A 对象上没有找到 x 属性，那么会沿着原型链找 x 属性；

面试题一： 简述 instance 的原理，并用代码实现

image.png

// 遍历链表
const instanceOf = (A, B) => {
   let p = A;
   while (p) {
       if (p === B.prototype) {
           teturn true;
       }
       p = p.__proto__;
   }
   return false;
}

面试题二：

var foo = {},
F = function(){};
Object.prototype.a = 'value a';
Object.prototype.b= 'value b';

console.log(foo.a);
console.log(foo.b);

console.log(F.a);
console.log(F.b);

image.png

// value a undefined
// value a value b

前端与链表： 使用链表指针获取 JSON 的节点值

const json = {
    a: { b: {c:1} },
    d: { e: 2}
}
const path = ['a', 'b','c'];

let p = json;
path.forEach(k => {
    p = p[k];
})