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\$
2
  • \$\begingroup\$ This is the same question as your previous one. Why do that? \$\endgroup\$ Mar 10, 2013 at 2:43
  • \$\begingroup\$ it's not the same one. The previous one keeps the duplicate(only one). \$\endgroup\$
    – Fihop
    Mar 10, 2013 at 4:29

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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