算法 - 链表

链表

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

数组 VS 链表

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

JS中的链表

• 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

// 遍历链表
let p = a
while (p) {
    console.log(p.val)
    p.next
}

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

// 删除
c.next = d

删除链表中的节点

leeCode第237题

• 无法得知链表指定的值上一位是什么，所以没法直接改变上一位的next指向
• 将指定项本身改为自身指定的下一项，就相当于删除了该节点并改变了指向

const deleteNode = function(node) {
    node.val = node.next.val // 将值改为链表的下一项的值
    node.next = node.next.next // 将本身的指向改为下一项的指向
}

反转链表

leeCode第206题

• 反转两个节点：将 n+1 的 next 指向 n
• 反转多个节点：双指针遍历链表，重复上述操作

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

/**
 * 将一个数组转为链表
 * @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)

此解法为双指针迭代，还有一种为迭代
播放量最多也最好懂的答案

两数相加

leeCode第206题

• 模拟相加操作
• 遍历被相加的两个链表，模拟相加操作，将个位数追加到新的链表上，将十位数留到下一个去相加

将数组转为链表上面已经提供了，下面就不再提供了

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

    while (l1 || l2) {
        const v1 = l1 ? l1.val : 0 // 因为两个链表长度不需要一样，所以可能对应不上
        const v2 = l2 ? l2.val : 0
        const val = v1 + v2 + carry
        carry = ~~(val / 10) // 取出10位数，不太直观就是将结果toString()取索引0

        if (!head) {
            head = tail = new ListNode(val % 10); // 创建链，头尾一致
        } else {
            tail.next = new ListNode(val % 10);
            tail = tail.next;
        }

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

    // 判断最后是否存在carry，有的话需要补到链表最后位
    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)

删除排序链表中的重复元素

leeCode第83题

• 链表已进行排序，所以重复元素一定相邻
• 遍历链表，如果发现当前元素和下一个元素值相同，就删除下个元素
• 遍历结束后，返回原链表的头部

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

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

环形链表

leeCode第141题

• 圆形操场上的起点同时起跑，速度快的一定会超过速度慢的一圈
• 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈

/**
 * @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
}

这道题实在不知道要怎么模拟，要模拟就必须在最后一位重写指向，入参就跟题目对不上了，只能去leeCode上去校验