82. Remove Duplicates from Sorted List II

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head)
    {
        if (!head || !head->next) return head;

        // 因為 head 有可能會有重複項
        // 如果刪掉就沒有了
        // 所以這裡定義一個新的節點 dummy
        ListNode* dummy = new ListNode(-1);
        // 用一個 prev 指標指到這個 pseudo node
        ListNode* prev = dummy;

        // 然後這個 dummy node 接到 head
        // 以避免 head 被刪掉的情況
        dummy->next = head;

        // 從下個位置開始走訪節點
        while (prev->next)
        {
            ListNode* cur = prev->next;
            // 跳過所有重複的節點
            while (cur->next && cur->val == cur->next->val)
            {
                cur = cur->next;
            }

            if (cur != prev->next)
            {
                // 略過重複的節點
                prev->next = cur->next;
            }
            else
            {
                // 移到下一個節點
                prev = prev->next;
            }
        }
        return dummy->next;
    }
};

• T: $O(n)$
• S: $O(1)$