重启DAY6 前后指针

跟着灵茶山艾府大佬学习算法思路的day6，目标是在一个月内掌握hot100

b站链接如下：

删除链表重复节点【基础算法精讲 08】

删除链表中的节点 题目描述：

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

• 给定节点的值不应该存在于链表中。
• 链表中的节点数应该减少 1。
• node 前面的所有值顺序相同。
• node 后面的所有值顺序相同。

自定义测试：

• 对于输入，你应该提供整个链表 head 和要给出的节点 node。node 不应该是链表的最后一个节点，而应该是链表中的一个实际节点。
• 我们将构建链表，并将节点传递给你的函数。
• 输出将是调用你函数后的整个链表。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

• 链表中节点的数目范围是 [2, 1000]
• -1000 <= Node.val <= 1000
• 链表中每个节点的值都是 唯一 的
• 需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

思路：

这题有些脑筋急转弯，不知道头结点的情况下，我们可以将下一个节点的值复制到已知的node节点，然后删除下一个节点就可以了，因为我们已知node不是末尾节点。

代码：

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

总结：

emmmmmm，有点难想，但一讲就通。

删除链表的倒数第 N 个结点 题目描述：

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

思路：

有些链表题需要创建dummyNode，但是有些不需要，对于可能删除头结点的题型，就可以创建一个dummyNode。这道题显然可以创建，但也可以针对删除头结点的情况单独处理。

这题第一种常规的思路是遍历链表，找到节点总数，就能知道倒数第n个节点是正数的哪一个节点，思路是比较清晰的。而第二种思路比较巧妙，如果要删除倒数第n个节点，需要找到倒数第n+1个节点。这时可以初始化right指向dummy，想让右指针走n步；然后初始化left也指向dummy，此时left和right一起移动，当右指针走到最后一个节点，此时left就正好指向n+1个节点。

代码：

第一种解法（无dummy）：

var removeNthFromEnd = function(head, n) {
    let len = 0;
    let count = head;
    while (count) { // 计算节点总数
        len++;
        count = count.next;
    }
    if (len === 1) return null;
    let nodenum = len - n; // 计算要删除的节点号数，以0开始计数

    if (nodenum === 0) return head.next;

    let pre = head;
    for (let i = 0; i < nodenum - 1; i++) {
        pre = pre.next;
    }
    pre.next = pre.next.next;

    return head;
};

第二种解法：

var removeNthFromEnd = function(head, n) {
    const dummyHead = new ListNode(0, head);
    let right = dummyHead;
    for (let i = 0; i < n; i++) {
        right = right.next;
    }

    let left = dummyHead;

    while (right.next) {
        left = left.next;
        right = right.next;
    }
    left.next = left.next.next;
    
    return dummyHead.next;
};

总结：

两种思路的代码构建都是比较顺畅的，就是在处理第二种思路的边界条件时，最好动笔模拟一下，要清楚right的第一次移动是从dummy开始，移动n-1步。

删除排序链表中的重复元素 题目描述：

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

思路：

由于已知是升序排列，是可以不删除头结点的，所以可以不使用dummy。如果下一个节点的值与本节点相同，就跳过下一个节点即可；如果不同，就可以来到下一个节点，并且回到上一步，继续进行值相同的判断。值得注意的是有可能链表为空，需要添加一个额外判断。

代码：

var deleteDuplicates = function(head) {

    let cur = head;
    while (cur && cur.next) { // 顺便判断链表是否为空
        if (cur.val === cur.next.val) {
            cur.next = cur.next.next;
        }
        else {
            cur = cur.next;
        }

    }
    return head;
    
};

总结：

比较简单，比较好想。

删除排序链表中的重复元素 II 题目描述：

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

思路：

这题相较于上一题，不一样的地方就在于需要删除所有相同的节点，那么头结点也可能会被删除，就需要dummy了。

怎么删除呢？可以在每次循环时看next和next.next的值是否一样，如果一样，可以再套一个循环，用以不断删除节点，直到没有节点，或者遇到的节点值不相同。如果不一样，当然就移向下一个节点。直到后面不足两个节点。

代码：

var deleteDuplicates = function(head) {
    const dummy = new ListNode(0, head);
    let cur = dummy;
    while (cur.next && cur.next.next) {
        let val = cur.next.val; // 在下面的循环中cur.next.val会改变，因此先记录下来
        if (cur.next.next.val === val) { // 如果值都是val的节点的个数大于等于两个
            // 就将包括cur.next在内值等于val的节点全部删除
            while (cur.next && cur.next.val === val) {
                cur.next = cur.next.next;
            }
        }
        else {
            cur = cur.next;
        }

    }
    return dummy.next;
};

总结：

这一题的思路稍微绕一些，关键在于理解节点个数和删除的关系，大于等于两个节点的值相同才是重复，此时就可以根据这个条件，将所有与cur.next值相同的后续节点全部删除。

值得注意的是虽然有两层循环，但每次执行if或者else的时间复杂度都是o(1)，所以总的时间复杂度是o(n)。