[daiy4] jz76 delete duplicate nodes in the linked list (recursion)

Title Description ：

reflection ：

The initial idea ： Make one set, Save all nodes without duplication val, Finally, it is combined into a linked list . Turn around and think about it , It's troublesome to combine into a new linked list .
It would be ,phead Take a step down , If the value appears in set in , Just go down , It should be ok ~
Oh dear , It's not as simple as I thought

  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

When it comes to testing , I found that I had made a mistake ！ No reservation val Duplicate values , It's all deleted ！ EH , I don't know if the duplicate values are pasted together . It's a sort list , So the same values must be together . So only in When the current node is different from the next node , Before you can join .

    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

The recursive method

Recursion again , Every time I see recursion, I have a headache ..

• Recursive export ： Consider what circumstances , We no longer need 「 Delete 」 operation . Obviously, when the parameters passed in pHead It's empty , perhaps pHead.next It's empty time , There must be no repeating elements , You can go back to pHead;
• The minimum operation of recursive link ： Then consider how to delete the logic ：
  obviously , When pHead.val != pHead.next.val when ,pHead It can be retained , So we just need to put pHead.next Pass in recursive functions , And return the value as pHead.next, Then return pHead that will do ;
  When pHead.val == pHead.next.val when ,pHead Cannot be retained , We need to use temporary variables tmp skip 「 And pHead.val A continuous segment with the same value 」, take tmp The result obtained by passing in the recursive function is returned as this time .

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)