鏈表

• 多個元素組成的列表
• 元素存儲不能連續(xù)，用next指針連在一起

數(shù)組 VS 鏈表

數(shù)組：增刪非首尾元素時往往需要移動元素
鏈表：增刪非首尾元素，不需要移動元素，只需要更改 next 指針即可

JS中的鏈表

• JS 中沒用鏈表
• 可以使用Object進(jìn)行模擬

遍歷鏈表

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.next
}

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

// 刪除
c.next = d

刪除鏈表中的節(jié)點(diǎn)

leeCode第237題

• 無法得知鏈表指定的值上一位是什么，所以沒法直接改變上一位的next指向
• 將指定項(xiàng)本身改為自身指定的下一項(xiàng)，就相當(dāng)于刪除了該節(jié)點(diǎn)并改變了指向

const deleteNode = function(node) {
    node.val = node.next.val // 將值改為鏈表的下一項(xiàng)的值
    node.next = node.next.next // 將本身的指向改為下一項(xiàng)的指向
}

反轉(zhuǎn)鏈表

leeCode第206題

• 反轉(zhuǎn)兩個節(jié)點(diǎn)：將 n+1 的 next 指向 n
• 反轉(zhuǎn)多個節(jié)點(diǎn)：雙指針遍歷鏈表，重復(fù)上述操作

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

/**
 * 將一個數(shù)組轉(zhuǎn)為鏈表
 * @param {array} arr
 * @return {ListNode}
 */
const getListFromArray = (arr) => {
    let dummy = new ListNode()
    let pre = dummy;
    arr.forEach(x => pre = pre.next = new ListNode(x));
    return dummy.next;
}

const reverseList = function(head) {
    let p1 = head
    let p2 = null

    while (p1) {
        const tmp = p1.next
        p1.next = p2
        p2 = p1
        p1 = tmp

        console.log(p1, p2)
    }

    return p2
};

let listNodes = getListFromArray([1, 2, 3, 4, 5])

const res = reverseList(listNodes)
console.log(listNodes, res)

此解法為雙指針迭代，還有一種為迭代
播放量最多也最好懂的答案

兩數(shù)相加

leeCode第206題

• 模擬相加操作
• 遍歷被相加的兩個鏈表，模擬相加操作，將個位數(shù)追加到新的鏈表上，將十位數(shù)留到下一個去相加

將數(shù)組轉(zhuǎn)為鏈表上面已經(jīng)提供了，下面就不再提供了

var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;

    while (l1 || l2) {
        const v1 = l1 ? l1.val : 0 // 因?yàn)閮蓚€鏈表長度不需要一樣，所以可能對應(yīng)不上
        const v2 = l2 ? l2.val : 0
        const val = v1 + v2 + carry
        carry = ~~(val / 10) // 取出10位數(shù)，不太直觀就是將結(jié)果toString()取索引0

        if (!head) {
            head = tail = new ListNode(val % 10); // 創(chuàng)建鏈，頭尾一致
        } else {
            tail.next = new ListNode(val % 10);
            tail = tail.next;
        }

        if (l1) l1 = l1.next
        if (l2) l2 = l2.next
    }

    // 判斷最后是否存在carry，有的話需要補(bǔ)到鏈表最后位
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }

    return head
};

const l1 = getListFromArray([2,4,3])
const l2 = getListFromArray([5,6,4])
addTwoNumbers(l1, l2)

刪除排序鏈表中的重復(fù)元素

leeCode第83題

• 鏈表已進(jìn)行排序，所以重復(fù)元素一定相鄰
• 遍歷鏈表，如果發(fā)現(xiàn)當(dāng)前元素和下一個元素值相同，就刪除下個元素
• 遍歷結(jié)束后，返回原鏈表的頭部

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const deleteDuplicates = function(head) {
    let p = head
    while (p && p.next) {
        if (p.val === p.next.val) { // 當(dāng)前與下一個值相同，則刪除下一個值
            p.next = p.next.next
        } else {
            p = p.next
        }
    }
    return head
}

const duplicateLink = getListFromArray([1,1,1,2,3,3])
console.log(deleteDuplicates(duplicateLink))

環(huán)形鏈表

leeCode第141題

• 圓形操場上的起點(diǎn)同時起跑，速度快的一定會超過速度慢的一圈
• 用一快一慢兩個指針遍歷鏈表，如果指針能夠相逢，那么鏈表就有圈

/**
 * @param {ListNode} head
 * @return {boolean}
 */
const 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
}

這道題實(shí)在不知道要怎么模擬，要模擬就必須在最后一位重寫指向，入?yún)⒕透}目對不上了，只能去leeCode上去校驗(yàn)