关于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)。