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

Original 彭哥数据结构和算法 2022-05-19

问题描述

来源：LeetCode第82题

难度：中等

存在一个按升序排列的链表，给你这个链表的头节点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
题目数据保证链表已经按升序排列

双指针解决

前面我们刚讲过595，删除排序链表中的重复元素，这题和595题不同的是，如果有数字相同的节点，那么这些数字相同的节点要全部删除。

这题的解决思路就是使用两个指针，一个指针cur指向当前节点，一个指针pre指向当前节点cur的前一个节点。cur始终和他的下一个节点比较，如果相同就往后移，如果不相同我们就需要判断pre的下一个节点是否是cur，如果是cur说明没有相同的节点，如果不是cur说明有相同的节点，我们就要删除，叙述不太好理解，我做个视频来看一下

最后在来看下代码

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)
        return head;
    //添加一个dummy节点
    ListNode dummy = new ListNode(0);
    //让dummy节点的next指针指向head。
    dummy.next = head;
    //指向当前遍历的节点
    ListNode cur = head;
    //指向当前节点pre的前一个节点
    ListNode pre = dummy;
    while (cur != null) {
        while (cur.next != null && cur.val == cur.next.val) {
            //如果有重复的，cur就一直往下走
            cur = cur.next;
        }
        //判断上面有没有重复的节点，如果pre.next == cur，说明没有
        //重复的节点。否则说明有重复的节点，然后还要把重复的节点给删除
        if (pre.next == cur) {
            pre = pre.next;
        } else {
            //有重复的就删除
            pre.next = cur.next;
        }
        cur = cur.next;
    }
    return dummy.next;
}

递归方式解决

除了上面的方式以外，我们还可以使用递归的方式来解决，我们先定义一个函数deleteDuplicates(ListNode head)表示删除重复的节点。

如果head.val != head.next.val，也就是说当前节点和他的下一个节点值不一样，我们不做任何的删除，直接递归head节点的下一个节点，也就是

head.next = deleteDuplicates(head.next);

如果head.val == head.next.val，说明有重复的节点，这里到底是重复一个还是重复多个，我们不知道，需要通过一个循环来确定。然后把重复的全部删除，也就是

while (head.next != null && head.val == head.next.val) head = head.next;return deleteDuplicates(head.next);

那递归的终止条件是什么呢，就是节点为空，或者只有一个节点，这种情况下是不可能有重复的，直接返回即可。我们来看下完整代码

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)
        return head;
    if (head.val != head.next.val) {
        //如果当前节点和下一个节点的值不相同
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
        //如果当前节点和下一个节点的值相同，说明出现了重复的，
        //把重复的全部给删除
        while (head.next != null && head.val == head.next.val)
            head = head.next;
        return deleteDuplicates(head.next);
    }
}