链表 - 删除系列

来源：基础算法精讲 by 灵茶山艾府

视频精讲：链表 - 删除系列

题目	代码	备注
237. 删除链表中的节点	代码	脑筋急转弯
19. 删除链表的倒数第 N 个结点	代码	前后指针
83. 删除排序链表中的重复元素	代码
82. 删除排序链表中的重复元素 II	代码
203. 移除链表元素	代码	*课后作业
3217. 从链表中移除在数组中存在的节点	代码	*课后作业
2487. 从链表中移除节点	代码	*课后作业

例题

237. 删除链表中的节点

• 值覆盖，next覆盖即可

19. 删除链表的倒数第 N 个结点

• 注意，需要引入dummy节点的情况通常是会对头节点有相关操作，可能是倒数第length个，所以要引入dummy
• 法一，m+n===length，计算出m再移动即可
• 法二，双指针，r移动n步，然后l，r一起移动直到 r.next ===null;
• 不要忘记new操作符

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
    const dummy = new ListNode(0, head);
    let l = dummy, r = dummy;

    while (r && n--) r = r.next;
    // console.log('beforeBL', r)
    while (r && (r.next !== null)) {
        r = r.next;
        l = l.next;
    }
    if (l) {
        l.next = l.next.next;
    }
    // console.log('aftBL', l, r, dummy)
    return dummy.next;
};

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

• 一些细节问题，val，迭代逻辑

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    let curr = head;

    while (curr && (curr.next !== null)) {
        //不要下意识使用value，造成奇奇怪怪的错误，这里用val
        if (curr.val === curr.next.val) {
            curr.next = curr.next.next;
        } else
            curr = curr.next;
    }
    // console.log('curr',curr,'head',head);
    return head;
};

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

• 多画图模拟，画图模拟；

 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
    const dummy = new ListNode(0, head)
    let curr = head, pre = dummy;
    //重新梳理逻辑：当遇到重复值，要找出所有重复值，找完之后pre再进行移动
    while (curr && curr.next) {
        if (curr.val === curr.next.val) {
            //找到重复值的最后一个
            while (curr && curr.next && (curr.val === curr.next.val)) {
                curr = curr.next
            }
            pre.next = curr.next;
            //防止有连续的重复值
            curr = curr.next

        } else {
            //清除逻辑，跳过连续或者不连续的
            pre = curr;
            curr = curr.next;
        }
        // console.log(pre.val, curr.val, dummy)

    }
    return dummy.next;

作业