链表

什么是链表

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

数组vs链表

• 数组: 增删非首尾元素时，需要移动元素
• 链表: 增删非首尾元素时, 更改next指针就行

模拟链表

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;
// 遍历链表
// 定义指针
let p = a
while(p){
    console.log(p.val)
    p = a.next
}
// 插入e到c和d中间
const e = {val: 'e'}
c.next = e
e.next = d
// 删除e
c.next = d

删除链表中的节点（leetcode 237）

解题思路

• 无法直接获取被删除节点的上个节点
• 将被删除节点转移到下个节点

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

反转链表

• 如果反转两个节点，则将n+1的next指向n
• 反转多个节点，双指针遍历链表，重复操作，直到结尾

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
    var pre = null
    var current = head
    while (current !== null) {
        // 交换
        var next = current.next
        current.next = pre
        // 往后挪
        pre = current
        current = next
    }
    return pre
};

链表相加(leetcode 2)

解题思路

1. 用两个指针遍历两个节点，相加
2. 如果相加值>9,则把十位数放到下一轮节点相加，个位数放在该节点

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

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    let 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;
};

环形链表(leetcode 141)

// 快慢指针，如果有环形，则肯定会相遇
function hasCicle (head) {
    let slow = head
    let fast = head
    while (slow && fast && fast.next) {
        slow = slow.next
        fast = fast.next.next
        if(slow === fast) {
            return true
        }
    }
    return false
}
// 标记法,每个遍历过的节点，增加标记
function hasCicle (head) {
    let p = head
    while (p) {
        if(p.tag){
            return true
        }
        p.tag = true
        p = p.next
    }
    return false
}

原型链

原型链的本质是链表，链表通过next进行连接，对象通过proto进行连接

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

知识点

• 如果A沿着原型链能招找B.prototype, 那么A instanceof b 为true

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

• 如果在A对象上没有招到x属性，那么会沿着原型链寻找x属性

var foo = {},
    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

实践

const json = {
    a: {b: {c: 1}}
}
const path = ['a','b', 'c']
let p = json
path.forEach(item => {
    p = p[item]
})