关于leetcode:完虐算法删除有序链表中重复的元素I

更多算法常识，请关注公众号《程序员学长》

删除有序链表中反复的元素 -II

问题形容

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

存在一个按升序排列的链表，给你这个链表的头节点 head，请你删除链表中所有存在数字反复状况的节点，只保留原始链表中没有反复呈现的数字。返回同样按升序排列的后果链表。

示例:

输出：head = [1，2，3，3，4，5]

输入：[1，2，5]

剖析问题

因为给定的链表是有序的， 所以链表中反复的元素在地位上必定是相邻的 。因而，咱们能够对链表进行一次遍历，就能够删除反复的元素。

这里须要留神一点，因为可能会删除头结点 head，咱们引入了一个哨兵节点 dummy，让 dummy.next=head，这样即便 head 被删除了，那么也会操作 dummy.next 指向新的链表头结点，所以最终返回 dummy.next 即可。

首先，咱们让 cur 指针指向链表的哨兵节点，而后开始对链表进行遍历。如果 cur.next 与 cur.next.next 对应的元素值雷同，那么咱们就须要将 cur.next 以及前面所有值雷同的链表节点全副删除，直到 cur.next 为空节点或者其元素值与其不同。如果 cur.next 与 cur.next.next 对应的元素值不雷同，那么咱们就能够将 cur 指向 cur.next。

上面咱们来看一下代码的实现。

class Solution:
    def deleteDuplicates(self, head):
        #如果链表为空，间接返回
        if not head:
            return head
        #创立一个哨兵节点
        dummy = ListNode(0)
        dummy.next=head

        #开始时，将 cur 指向哨兵节点
        cur = dummy
        while cur.next and cur.next.next:
            #如果 cur.next.val 和 cur.next.next.val 雷同，删除反复元素
            if cur.next.val == cur.next.next.val:
                data = cur.next.val
                while cur.next and cur.next.val == data:
                    cur.next = cur.next.next
            else:
                cur = cur.next

        return dummy.next

该算法的工夫复杂度是 O(n)，空间复杂度是 O(1)。