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

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

image.png

解题思路：

1. 遍历链表两次，第一遍用set记录重复的元素，第二遍删除掉在set中列表元素；
2. 双指针遍历一次，先申请dummp节点，使dummp.next指向head，快指针指向head，慢指针指向dummp，开始遍历判断fast.next.val是否等于slow.next.val，若不等于，快慢指针同时前进一步，若相等，则使快指针一直前进直至fast.next.val != slow.next.val，此时使slow.next = fast.next，因为此时fast.val还是属于重复数字，然后使快指针前进一步，并继续遍历；跳出外循环，返回dummp.next。

Python3代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 遍历两次
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        p = head
        s = set()
        while head.next:
            if head.next.val == head.val:
                s.add(head.val)
                head.next = head.next.next
            else:
                head=head.next
        pre = ListNode(0)
        pre.next = p
        q = pre
        while q.next:
            if q.next.val in s:
                q.next = q.next.next
            else:
                q = q.next
        return pre.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# 双指针
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        dummp = ListNode(-1)
        dummp.next = head
        slow = dummp
        fast = head
        while fast and fast.next:
            if slow.next.val != fast.next.val:
                slow = slow.next
                fast = fast.next
            else:
                while fast and fast.next and slow.next.val == fast.next.val:
                    fast = fast.next
                slow.next = fast.next
                fast = fast.next
        return dummp.next