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

这道题要求在升序链表中删除所有重复出现的元素，仅保留只出现一次的节点，可以通过 双指针遍历。遍历链表时，先通过内层循环让cur跳到当前值的最后一个重复节点，然后判断pre的后继是否是cur—— 如果是，说明该节点有效，pre向前推进；如果不是，说明当前值是重复元素，直接让pre的后继指向cur的下一个节点，最后cur继续推进遍历。
ListNode* deleteDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }
 
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* pre = dummy;
    ListNode* cur = head;
 
    while (cur != nullptr) {
        while (cur->next != nullptr && cur->val == cur->next->val) {
            cur = cur->next;
        }
 
        if (pre->next == cur) {
            pre = pre->next;
        } else {
            pre->next = cur->next;
        }
        cur = cur->next;
    }
 
    ListNode* newhead = dummy->next;
    delete dummy;
    return newhead;
}

该解法的时间复杂度为 O (n)，空间复杂度为 O (1)