分析

• 本题的考点：链表。

• 因为头结点不会变，因此不需要虚拟头结点。

• 因为链表时升序排列的，因此重复的节点一定排在一起，我们用a、b分别指向两个相邻位置，只要a->val==b->val，我们就让a->next = b->next，然后b向后移动一位；如果a->val!=b->val，让a、b都向后移动一位，直到b为空。

代码

• C++

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

        if (!head || !head->next) return head;
        auto a = head, b = a->next;
        while (b) {
            if (a->val == b->val) a->next = b->next;
            else a = b;
            b = b->next;
        }
        return head;
    }
};

• Java

class Solution {
    public ListNode deleteDuplicates(ListNode head) {

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

        ListNode a = head, b = a.next;
        while (b != null) {
            if (a.val == b.val) a.next = b.next;
            else a = b;
            b = b.next;
        }
        return head;
    }
}

时空复杂度分析

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

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