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

题目

题目来源：力扣（LeetCode）

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。

示例 1：

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

示例 2：

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

思路分析

双指针法

由题意可知，给定的链表已经是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

1、删除重复元素时链表的头节点可能会被删除，因此我们需要定义一个虚拟头节点，其后继指针指向链表的头节点：
2、定义一个 prev 指针指向虚拟头节点 dummyHead，用以将删除重复节点之后剩余的链表部分连接起来；定义一个 curr 指针，指向头节点

3、遍历链表，如果 curr 指针所指向节点的值与curr指针所指向节点的下一个节点的值相等，那么curr指针往后移动一位，prev指针则保持不动：
4、如果 curr 指针所指向节点的值与curr指针所指向节点的下一个节点的值不相等，则将prev指针所指向节点的后继指针指向 curr指针所指向节点的后一个节点，然后将 curr 指针往后移动一位：
5、接着将prev指针指向curr指针所指向的节点，然后curr指针则往后移动一位：
6、当curr.next指向null时，说明链表已经遍历完毕，链表中所有重复元素也已删除

var deleteDuplicates = function(head) {
    if (head == null) return null;
    // 定义一个虚拟头节点，其后继指针指向头节点
    const dummyHead = new ListNode(-1, head);
    // 定义 prev 指针，初始时指向虚拟头节点
    let prev = dummyHead;
    // 定义 curr 指针，指向头节点
    let curr = prev.next;
    // 遍历链表
    while (curr != null && curr.next != null) {
        // 如果 curr 指针所指向的节点值与 curr 指针所指向节点的下一个节点的值不相等
        if (curr.val != curr.next.val) {
            // prev 指针往后移动一位
            prev = prev.next;
            // curr 指针往后移动一位
            curr = curr.next
        } else {
            // 如果 curr 指针所指向的节点值与 curr 指针所指向节点的下一个节点的值相等
            while (curr != null  && curr.next != null && curr.val === curr.next.val) {
                // curr 指针往后移动，直到找到 curr.val != curr.next.val
                curr = curr.next;
            }
            prev.next = curr.next;
            curr = curr.next
        }
    }
    return dummyHead.next;
};

单指针法

由于给定的链表是已经排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，即可删除重复的元素。

由于链表的头节点也可能被删除，因此我们需要先定义一个虚拟头节点来指向链表的头节点。

然后我们定义一个 curr 指针，指向链表的虚拟头节点，随后开始遍历链表，如果当前 curr.next 与 curr.next.next 所对应节点的值相等，那么我们就将 curr.next 以及后面与之相等的节点值的所有节点全部删除。我们记录下这个元素的值 x，随后不断将 curr.next从链表中删除，直到 curr.next 为空节点或者其节点值不等于 x 为止。此时，我们已经将链表中所有节点值为 x 的节点全部删除。

如果当前 curr.next 与 curr.next.next 所对应节点的值不相等，那么说明链表中只有一个节点值为 curr.next 的节点，那么我们就可以将 curr 指针指向 curr.next，即将curr指针往后移动一位。

当遍历完这个链表，所有重复的节点也已删除，我们返回返回链表的虚拟头节点的下一个节点。

var deleteDuplicates = function(head) {
    if (!head) return head;
    // 定义一个虚拟头节点
    const dummyHead = new ListNode(-1, head);
    // 定义一个 curr 指针，指向虚拟头节点
    let curr = dummyHead;
    // 遍历链表
    while (curr.next && curr.next.next) {
        // 当前 curr.next 与 curr.next.next 所对应节点的值相等
        // 将 curr.next 及所有后面与之相同元素值的链表节点全部删除
        if (curr.next.val === curr.next.next.val) {
            const x = curr.next.val;
            while(curr.next && curr.next.val === x) {
                curr.next = curr.next.next;
            }
        } else {
            // 当前 curr.next 与 curr.next.next 所对应节点的值不相等，将 curr 指针往后移动一位
            curr = curr.next
        }
    }
    // 链表遍历完成，返回链表虚拟头节点的下一个节点
    return dummyHead.next;
};