current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 2 down vote favorite

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;
}
share|improve this question
    
Are the nodes dynamically allocated. If so you are leaking. – Loki Astari Mar 9 '13 at 18:48
    
yes, I don't write code to free dynamically allocated memory~ – Fihop Mar 9 '13 at 19:40
    
Do the duplicates occur in quick succession or they can randomly be anywhere in the list? – Nash Vail Dec 29 '14 at 14:36
up vote 3 down vote

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
up vote 0 down vote

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 '13 at 20:47
    
Oh, you're right I didn't notice the "sorted" – Thüzhen Mar 9 '13 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.