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

题目要求

解题思路

题意：在一个有序链表中，如果一个节点的值出现不止一次，那么把这个节点删除掉
重点：有序链表，所以，一个节点的值出现不止一次，那么他们必相邻。

方法一：递归

链表和树的问题，一般都可以有递归和迭代两种写法。对于本题一定要记住是有序链表，值相同的节点会在一起。
1.1 递归函数定义
递归最基本的是要明白递归函数的定义！
递归函数直接使用题目给出的函数deleteDuplicates(head)，它的含义是删除以head作为开头的有序链表，值出现重复的节点。
1.2 递归终止条件
终止条件就是能想到的基本的、不用继续递归处理的case

• 如果head为空，那么肯定没有值出现反复的节点，直接返回head；
• 如果head.next为空，那么说明链表中只有一个节点，也没有值出现重复的节点，也直接返回head

1.3 递归调用
什么时候需要调用递归呢？我们考虑两种情况：

• 如果head.val != head.next.val，说明头节点的值不等于下一个节点的值，所以当前的head节点必须保留；但是head.next节点要不要保留呢？我们还不知道，需要head.next进行递归，即对head.next作为头节点的链表，去除值重复的节点。所以head.next = self.deleteDuplicates(head.next)
• 如果head.val == head.next.val，说明头节点的值等于下一个节点的值，所以当前的head，节点必须删除；但是head.next节点要不要删除呢？我们还不知道，需要一直向后遍历寻找与head.val不等的节点。与haed.val相等的这一段链表都要删除，因此返回deleteDuplicates(move)；

1.4 返回结果
题目让我们返回删除了值重复的节点后剩余的链表，结合上面两种递归调用的情况。

• 如果head.val != head.next.val，头节点需要保留，因此返回的是head；
• 如果head.val == head.next.val，头节点需要删除，需要返回的是deleteDuplicates(move)。

迭代

方法二：一次遍历

这里说的一次遍历，是说一次遍历、一遍统计相邻节点的值是否相等，如果值相等就继续后移找到值不等的位置，然后删除值相等的这个区间
其实这个思路很简单，跟递归方法中的while语句跳过所有值相等的节点的思路是一样的：如果curr.val == cur.next.val说明两个相邻节点值相等，所以继续猴戏，一直找到cur.val !=cure.next.val，此时的cur.next就是值不等的节点；
代码中用到了一个常见的技巧：dummy节点，也叫做哑节点。
它在链表的迭代写法中非常常见，因为对于本题而言，我们可能会删除头节点head，为了维护一个不变的头节点，所以我们添加了dummy，让dummy.next = head，这样即使头节点被删除了，那么操作dummy.next指向新的链表头部，所以最终返回的也是dummy.next

方法三：利用计数，两次遍历

这个做法忽略了链表有序这个性质，使用了两次遍历，第一次遍历统计每个节点的值出现的次数，第二次遍历的时候，如果发现head.next的val出现次数不是1次，则需要删除head.next

代码

递归：

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        if head.val != head.next.val:
            head.next = self.deleteDuplicates(head.next)
        else:
            move = head.next
            while move and head.val == move.val:
                move = move.next
            return self.deleteDuplicates(move)
        return head

迭代：
一次遍历：

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy
        cur = head
        while cur:
            while cur.next and cur.val ==cur.next.val:
                cur = cur.next
            if pre.next ==cur:
                pre = pre.next
            else:
                pre.next = cur.next
            cur =cur.next
        return dummy.next

两次遍历：

class Solution:
    def deleteDuplicates(self, head):
        dummy = ListNode(0)
        dummy.next = head
        val_list = []
        while head:
            val_list.append(head.val)
            head = head.next
        counter = collections.Counter(val_list)
        head = dummy
        while head and head.next:
            if counter[head.next.val] != 1:
                head.next = head.next.next
            else:
                head = head.next
        return dummy.next

复杂度分析

递归：
时间复杂度：$O(N)$
空间复杂度：$O(N)$

迭代：
一次遍历
时间复杂度：$O(N)$
空间复杂度：$O(1)$

两次遍历
时间复杂度：$O(N)$
空间复杂度：$O(N)$