Remove duplicates from a linked list

Question

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;
}

Answer 1

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;
}

Answer 2

You could browse all the elements of the linked list and store their value, address, and the number of time they appear in an array. After that you just have to remove (form the linked list) the address stored in the array which correspond to values that appears more than once.

One advantage of this method is that you have to browse your linked list only once. on the other hand, you have to store all the value of your linked list in an array which uses more memory.