Well-defined invariant based concise c++ solution


  • 0
    S

    Note: the duplicate nodes are not being deleted in this code

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head)
        {
            if (!head || !head->next)
                return head;
            ListNode pre_new_head(0);
            pre_new_head.next = head;
            auto tail = &pre_new_head;
            /*
              Invariants:
              - tail is last node in the (new) list with only unique elements
              - tail->next is the next node whose uniqueness determination is pending
            */
            auto it = head;
            do {
                it = it->next;
                if (!it || it->val != tail->next->val) {
                    if (tail->next->next == it) // tail->next is unique
                        tail = tail->next;
                    tail->next = it;
                }
            } while (it);
            return pre_new_head.next;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.