Remove duplicates from a linked list

Given a sorted linked list, delete all duplicates such that each element appears only once.


For example:

• Given 1->1->2, return 1->2.

• Given 1->1->2->3->3, return 1->2->3.

The following is my code:

struct ListNode {
    int data;
    ListNode *next;
    ListNode(int x) : data(x), next(NULL) {}
};

ListNode *getNextElement(ListNode *head){   
    while ((head != NULL) && (head->next != NULL) 
          && (head->data == head->next->data)){
        head = head->next;      
    }

    return head->next;
}

ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    ListNode *cur = head;
    ListNode *next = NULL;
    while (cur != NULL){
        next = getNextElement(cur);
        cur->next = next;
        cur = next;
    }    
    return head;
}

head can never be NULL

ListNode *getNextElement(ListNode *head){   
    while ((head != NULL)                      // This can't be NULL
                                               // because you test before calling. 
          && (head->next != NULL) 
          && (head->data == head->next->data)){
        head = head->next;      
    }

    // If head can be NULL then you should also be checking here.
    // Otherwise this may fail.
    return head->next;
}

Small notes:

ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function

    // Replace with for(;;)
    for(ListNode* cur = head; cur != NULL; cur = cur->next){
        // Move declaration of next here.
        // It is not used outside the loop so why pollute
        ListNode *next = getNextElement(cur);

        // May want to make sure you don't leak.
        ListNode *old  = cur->next;
        while(old != next)
        {
            ListNode* toFree = old;  // you can probably put this logic in getNext()
            old = old->next;
            free(toFree);
        }
        cur->next = next;
    }    
    return head;
}

StackExchange Code Review Q#23670, answer score: 4