题解 | #升序链表的删除#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 
# @return ListNode类
#
class Solution:
    def deleteDuplicates(self , head: ListNode) -> ListNode:
        # write code here
        # 链表去重
        visited = set()
        def removeDu(head):
            if not head:
                return 0, head
            
            # hist
            ret, temphead = removeDu(head.next) # 看下一个是否需要remove

            # remove
            if ret: # 需要remove
                head.next = temphead.next # 删除递归前一个元素
                temphead.next = None
            
            # rec
            if head.val in visited:
                # 当前需要remove
                visited.add(head.val)
                return 1, head
            else:
                # 当前不需要remove
                visited.add(head.val)
                return 0, head

        dummy = ListNode(-1)
        dummy.next = head
        ans = removeDu(dummy)
        return ans[1].next

链表去重。我们知道链表去重需要知道重复链表的前一个节点，并进行操作。所以我们在每个节点时，需要知道下一个节点是否需要移除。判断是否需要移除就需要在外部保留一个set来记录所有出现过的val。所以一旦head.val出现在set里面，说明当前是重复，需要移除的head，所以将需要移除的状态传给递归中的下一层（链表中是上一个节点），上一个节点拿到历史记录后进行删除操作，并同时将自己是否需要删除传给上一个节点。