[牛客网刷题 Day4] JZ76 删除链表中重复的结点（递归）

题目描述：

思考：

刚开始的想法：弄一个set，存下所有节点的不重复val，最后再组合成链表。转头一想，组合成新链表好麻烦哦。
那就，phead往下走一步，如果值出现在set中，就再往下走，应该就可以啦~
哎呀，好像没有我想的那么简单呢

  if pHead is None:
            return None
        res = before = pHead
        num = set()
        while pHead:
            if pHead.val not in num:
                before = pHead
                num.add(pHead.val)
                pHead = pHead.next
            else:
                after = pHead
                while after and after.val in num:
                    after = after.next
                else:
                    before.next = after
                    pHead = pHead.next
        return res

测试的时候，发现我搞错题意了！不保留val重复的值哦，是全部删掉哦！诶，不知道重复值是不是贴一起的诶。说了是排序列表，所以相同的值一定在一起呢。所以只有在 当前节点和下一节点都不一样时，才可以加入哦。

    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        if pHead is None:
            return None
        res = dummy = ListNode(0)
        while pHead:
            if pHead.next is None:
                dummy.next = pHead
                break
            if pHead.val != pHead.next.val:
                dummy.next = pHead
                dummy = dummy.next
                pHead = pHead.next
            else:
                repeat = pHead.val
                while pHead.val == repeat:
                    pHead = pHead.next
                    if pHead is None:
                        dummy.next = None
                        break
        return res.next

递归解法

又是递归，每次看到递归就头疼。。

• 递归出口：考虑什么情况下，我们不再需要「删除」操作。显然当传入的参数 pHead 为空，或者 pHead.next 为空时，必然不存在重复元素，可直接返回 pHead；
• 递归环节的最小操作：之后再考虑删除逻辑该如何进行：
  显然，当 pHead.val != pHead.next.val 时，pHead 是可以被保留的，因此我们只需要将 pHead.next 传入递归函数，并将返回值作为 pHead.next，然后返回 pHead 即可；
  当 pHead.val == pHead.next.val 时，pHead 不能被保留，我们需要使用临时变量 tmp 跳过「与 pHead.val 值相同的连续一段」，将 tmp 传入递归函数所得的结果作为本次返回。

class Solution:
    def deleteDuplication(self , pHead: ListNode) -> ListNode:
        # write code here
        if pHead == None or pHead.next == None:
            return pHead
        if pHead.val != pHead.next.val:
            pHead.next = self.deleteDuplication(pHead.next)
            return pHead
        else:
            tmp = pHead
            while tmp!=None and tmp.val == pHead.val:
                tmp =tmp.next
            return self.deleteDuplication(tmp)