1
\$\begingroup\$

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.

The following is my code:

ListNode *getNextElement(ListNode *head, bool& repeated){   
    while ((head->next) != NULL &&
            (head->val == head->next->val)){        
        head = head->next;
        repeated = true;            
    }

    return head->next;
}

ListNode *deleteDuplicates(ListNode *head) {
    ListNode *result = NULL;
    ListNode *copy_result = result;
    ListNode *next = NULL;

    for (ListNode *cur = head; cur != NULL; cur = next){
        bool cur_repeat = false;
        next = getNextElement(cur, cur_repeat);

        if (cur_repeat == true){
            while(cur!=next){
                ListNode *toFree = cur;
                cur = cur->next;
                delete toFree;
            }
        }
        else{
            if(result == NULL){
                result = cur;
                copy_result = result;
            }
            else{
                result->next = cur;
                result = result->next;
            }           
        }
    }

    if(result != NULL)
        result->next = NULL;
    return copy_result;
}
\$\endgroup\$
  • \$\begingroup\$ This is the same question as your previous one. Why do that? \$\endgroup\$ – William Morris Mar 10 '13 at 2:43
  • \$\begingroup\$ it's not the same one. The previous one keeps the duplicate(only one). \$\endgroup\$ – Fihop Mar 10 '13 at 4:29
1
\$\begingroup\$

Iterate through the list and remember the pointer to the first element in the group node. Then check if the current element has the same value as the first element in the group. Remove the current element and set some flag to remember to remove the first element in this group. Then if you have a new value, set the first element pointer to this value and do it all over again.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.