Remove Duplicates from Sorted List II

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.
--------------------------------- thinking ---------------------------------------
corner case: 1->1->1
while (nxt) will return if nxt reaches to the end, so we still need to do additional checking for cur->next == NULL or not
------------------------------- codes ---------------------------------------
/**
 * 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) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode tmphead(-1);
        tmphead.next = head;
        ListNode *pre = &tmphead;
        ListNode *cur = head;
        ListNode *nxt = cur->next;
        bool is_dup = false;
        while (nxt) {
            if (nxt->val == cur->val) {
                nxt = nxt->next;
                is_dup = true;
            } else {
                if (is_dup) {
                    pre->next = nxt;
                } else {
                    pre = cur;
                }
                is_dup = false;
                cur = nxt;
                nxt = cur->next;
            }
        }
        //bug here
        if (cur->next != NULL) {
            pre->next = NULL;
        }
        return tmphead.next;
    }
}; 
----------------------------------- codes --------------------------------------------------------------------------------
/**
 * 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) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode dummy(-1);
        dummy.next = head;
        
        ListNode *cur = &dummy;
        while (cur && cur->next) {
            bool has_dup = false;
            ListNode *comp = cur->next->next;
            //the only defect of this method is all useless nodes are not freed!
            while (comp && comp->val == cur->next->val) {
                comp = comp->next;
            }
            if (comp != cur->next->next) {
                cur->next = comp;
            } else {
                //bug here -> only update cur when there is no duplication
                cur = cur->next;
            }
        }
        return dummy.next;
    }
};
------------------------------------ good codes -------------------------------------------------------------------------
class Solution { public: ListNode *deleteDuplicates(ListNode *head) { ListNode **runner = &head; if(!head || !head->next)return head; while(*runner) { if((*runner)->next && (*runner)->next->val == (*runner)->val) { ListNode *temp = *runner; while(temp && (*runner)->val == temp->val) temp = temp->next; *runner = temp; } else runner = &((*runner)->next); } return head; } };