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

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

Question

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

返回同样按升序排列的结果链表。

Example 1:

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

Example 2:

输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5 输出：[7,9,6,6,8,7,3,0,9,5]

Example 3:

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

提示：

链表中节点数目在范围 [0, 300] 内

-100 <= Node.val <= 100

题目数据保证链表已经按升序排列

Approach 1: 顺序遍历搜索

由于链表已经排序，因此要找到链表中重复的数字可以只用对比本节点的值和下一个节点的值，而不需使用HASH表。

注意：

头节点可能要修改，需要添加哑头节点；
始终对比 cur.next.val 和 cur.next.next.val，避免要寻找上一个节点；
注意 cur 和 dummy 怎么使用；

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 判断链表非空
        if not head:
            return head
        # 头节点可能要修改，需要添加哑头节点
        dummy = ListNode([])
        dummy.next = head
        cur = dummy

        while cur.next and cur.next.next:
            if cur.next.val == cur.next.next.val:
                x = cur.next.val
                while cur.next and cur.next.val == x:
                    cur.next = cur.next.next
            else:
                cur = cur.next
        return dummy.next



def main():
    head = stringToListNode([1,2,3,3,3,4,4,5])
    solution=Solution().deleteDuplicates(head)
    print(solution)

复杂度分析

时间复杂度：O(n)，其中 n 是链表的节点数量
空间复杂度：O(1)，增加了常数个指针。

Approach 2: 递归

递归最基本的是要明白递归函数的定义！

递归函数直接使用题目给出的函数 deleteDuplicates(head) ，它的含义是删除以 head 作为开头的有序链表中，值出现重复的节点。

终止条件就是能想到的基本的、不用继续递归处理的case。

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

什么时候需要递归呢？我们想一下这两种情况：

如果 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 之后所有与 head.val 相等的节点也都需要删除；删除到哪个节点为止呢？需要用 move 指针一直向后遍历寻找到与 head.val 不等的节点。此时 move 之前的节点都不保留了，因此返回 deleteDuplicates(move);

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

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

class Solution:
    def deleteDuplicates1(self, head):
        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

复杂度分析

时间复杂度：O(N)，每个节点访问了一次。
空间复杂度：O(N)，递归调用的时候会用到了系统的栈。