分析

• 本题的考点：链表。

• 因为原链表的头结点可能会变化，因此需要使用虚拟头结点。

• 因为链表时升序排列的，因此重复的节点一定排在一起，我们用a指向某段重复数字的前一个位置，b指向第一个重复元素，c指向最后一个重复元素的后一个位置，如果b->next != c，说明这段重复元素的个数多于1个，应该删除，否则不应该删除，如下图：

代码

• C++

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        if (!head || !head->next) return head;

        auto dummy = new ListNode(-1);
        dummy->next = head;

        auto a = dummy, b = a->next, c = b->next;
        while (c) {
            while (c && b->val == c->val) c = c->next;
            if (b->next != c) a->next = c;  // 说明含有重复元素
            else a = b;

            b = c;
            if (c) c = c->next;
        }
        return dummy->next;
    }
};

• Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        if (head == null || head.next == null) return head;

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode a = dummy, b = a.next, c = b.next;
        while (c != null) {
            while (c != null && b.val == c.val) c = c.next;
            if (b.next != c) a.next = c;
            else a = b;

            b = c;
            if (c != null) c = c.next;
        }
        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(1)$。