3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Are the nodes dynamically allocated. If so you are leaking. \$\endgroup\$ – Martin York Mar 9 '13 at 18:48
  • \$\begingroup\$ yes, I don't write code to free dynamically allocated memory~ \$\endgroup\$ – Fihop Mar 9 '13 at 19:40
  • \$\begingroup\$ Do the duplicates occur in quick succession or they can randomly be anywhere in the list? \$\endgroup\$ – Nash Vail Dec 29 '14 at 14:36
  • \$\begingroup\$ @Fihop Hey, I really like the simplicity of your solution. Is it possible to do this recursively instead of using a while loop? I've tried a couple varieties but they all mess up with edge cases. \$\endgroup\$ – takanuva15 Sep 20 '17 at 12:04
4
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ Hey, I really like the simplicity of your solution. Is it possible to do this recursively instead of using a while loop? I've tried a couple varieties but they all mess up with edge cases. \$\endgroup\$ – takanuva15 Sep 18 '17 at 16:17
  • 1
    \$\begingroup\$ @takanuva15: I did not write this I just wrote a review on it. Look above to the OP. \$\endgroup\$ – Martin York Sep 20 '17 at 2:43
  • \$\begingroup\$ Oops yeah, I see that now; srry \$\endgroup\$ – takanuva15 Sep 20 '17 at 12:05
0
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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