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

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

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

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

示例 1：

解法：

搞三个指针，pre,cur,tail

cur与tail用于比较是否重复，pre指针是cur的前一个指针。

如果检测到发生重复，pre指针直接等于迭代后的tail，然后cur等于pre.next，tail=cur.next。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head == None:
            return head
        dummy = ListNode(next=head)

        pre = dummy
        cur = pre.next  # 实际上是head的下一个
        tail = cur.next # 实际上是head的下一个

        while cur  != None and cur.next != None:
            flag = 0
            while tail != None and cur.val == tail.val:
                flag = 1
                tail = tail.next 

            if flag == 0:
                pre = cur # 临时保存
                cur = tail
                tail= cur.next
            else:
                
                pre.next = tail
                cur = pre.next
                if tail == None:
                    tail = None
                else:
                    tail = cur.next
        return dummy.next

官方题解

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node）指向链表的头节点。

具体地，我们从指针 cur指向链表的哑节点，随后开始对链表进行遍历。

如果当前 cur.next与cur.next.next 对应的元素相同，那么我们就需要将cur.next 以及所有后面拥有相同元素值的链表节点全部删除。

我们记下这个元素值 xx，随后不断将 cur.next 从链表中移除，直到 cur.next 为空节点或者其元素值不等于 xx 为止。此时，我们将链表中所有元素值为 xx 的节点全部删除。

如果当前cur.next 与cur.next.next 对应的元素不相同，那么说明链表中只有一个元素值为cur.next 的节点，那么我们就可以将cur 指向 cur.next。

当遍历完整个链表之后，我们返回链表的的哑节点的下一个节点dummy.next 即可。

class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if not head:
            return head
        
        dummy = ListNode(0, head)

        cur = dummy # 相当于pre指针
        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