Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Given a sorted linked list, delete all duplicates such that each element appear 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;
}
share|improve this question
Are the nodes dynamically allocated. If so you are leaking. – Loki Astari Mar 9 at 18:48
yes, I don't write code to free dynamically allocated memory~ – FihopZz Mar 9 at 19:40

3 Answers

Looks a little complicated. How about:

ListNode *deleteDuplicates(ListNode *head)
{
    ListNode *cur = head; 
    while (cur != NULL) {
        ListNode *next = cur->next;
        if ((next != NULL) && (next->data == cur->data)) {
            cur->next = next->next;
            free(next);
        } else {
            cur = next;
        }
    }
    return head;
}
share|improve this answer

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;
}
share|improve this answer

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.

share|improve this answer
1  
The list is sorted to begin with, so you only need to go through it once in either way. – Christopher Creutzig Mar 9 at 20:47
Oh, you're right I didn't notice the "sorted" – Thüzhen Mar 9 at 21:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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