C++ Solution w/ Explaination. 8ms, O(n) time, O(1) space


  • 0
    C

    Core Idea:
    The idea is the create three pointers, point to first, second and third nodes in series. If all three values are different(first /= second, second /= third), then the second node is Definitely unique(then Chain That Node Up!). otherwise. we continue to search (by shifting every pointers to the right by 1 unit).

    Key Words: 3 pointers, dummy node, compare middle node with first and third nodes.

    Programming Logics:
    step1: if there is no nodes or only one node, then return.
    step 2: create a dummy node with value does NOT equal to first or second node's value, later this dummy node is used to connect all unique nodes in the list.
    step 3: set three pointers, (first, second and third) first one point to dummy node, second one to the 1st(head) node, third one to the 2nd(head->next) node.
    step 4: while second node is not NULL, if three nodes all has unique values (OR first node is not equals to the second one and the third node is NULL, which may happened at the last node), then chain the second node into the list( lead by that dummy node), because the second node is definitely unique. if not don't do anything.
    step 5: no matter the second one is unique or not, Shift all three pointers to the right by 1 node.

    Code:

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if(!head||!head->next)
                return head;
            
            ListNode* It = new ListNode(head->val-1);
            ListNode* newHead = It;//It is the dummy node
            ListNode *one = It,  *two = head, *three = head->next;
            
            while(two){
                if(one->val!=two->val && (!three || two->val!=three->val)) {
                    It->next = two;
                    It = two;
                    It->next=NULL;
                }
                one = two;
                two = three;
                if(three)
                    three = three->next;
            }
            
            return newHead->next;
        }
    };
    

Log in to reply
 

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