[Leetcode] Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

Analysis:

We notice that a node is distinct if the node value is not equal to both its previous node value and next node value. So simply taking these node out would be the solution. Note you need to take care of the NULL previous and next node. Use a temporary new head to decrease the code complexity.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {

        ListNode* newHead = new ListNode(0);
        ListNode* p = newHead;
        ListNode* prev = NULL;
        while(head != NULL)
        {
            if ((prev == NULL || (prev != NULL && head->val != prev->val)) &&
                (head->next == NULL || (head->next != NULL && head->val != head->next->val)))
            {
                p->next = head;
                p = p->next;
            }
            prev = head;
            head = head->next;
        }
        p->next = NULL;
        head = newHead->next;
        delete newHead;
        return head;
    }
};

//solution 2:
ListNode *deleteDuplicates(ListNode *head) {
    ListNode* dummyHead = new ListNode(0);
    dummyHead->next = head;
    ListNode* curr = head;
    ListNode* prev = dummyHead;
    while(curr != NULL && curr->next != NULL)
    {
        if (curr->val == curr->next->val)
        {
            while(curr->next != NULL && curr->val == curr->next->val)
            {
                ListNode* tmp = curr->next;
                prev->next = curr->next;
                delete curr;
                curr = tmp;
            }
            //remove the last element
            ListNode* tmp = curr->next;
            prev->next = curr->next;
            delete curr;
            curr = tmp;  
            
        }
        else
        {
            prev = curr;
            curr = curr->next;
        }
    }
    
    return dummyHead->next;
}