Take the 2-minute tour ×
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 nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example, Given 1->2->3->3->4->4->5, return 1->2->5. Given 1->1->1->2->3, return 2->3.

**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
    struct ListNode* deleteDuplicates(struct ListNode* head) {
    }

I have the written the solution for it, but looking for more ideas and suggestions. This solution has passed all the 166 test cases from leetcode.

    /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
 struct ListNode * current = head, *nextNode, *temp;


 //No elements
 if(head == NULL)
 {
     return NULL;
 }

 //Single element linked list
 if(head->next == NULL)
 {
     return head;
 }

     //if the numbers are repeating from the beginning;;
     //then we need to move head;
     while(head !=NULL && head->next !=NULL && head->val == head->next->val){
     if( head->val == head->next->val)
     {
         nextNode = head->next;
         while(nextNode !=NULL  && head->val == nextNode->val){
            temp = nextNode;
        nextNode = nextNode->next;
            free(temp);
         }

         temp = head;
         head = nextNode;
         current = head;
         free(temp);
     }

     }
     //Again a check to see if the list is empty

         if(head == NULL)
         {
             return NULL;
         }


    while(current->next != NULL){

     nextNode = current->next;



        if(nextNode->next !=NULL  && nextNode->val == nextNode->next->val){         

         while(nextNode->next !=NULL  && nextNode->val == nextNode->next->val){
            temp = nextNode->next;
        nextNode->next = temp->next;
         }
        current->next = nextNode->next;

        }else {
            current = nextNode;   
        }

 }

return head;


}
share|improve this question

migrated from stackoverflow.com Jul 27 at 11:57

This question came from our site for professional and enthusiast programmers.

1 Answer 1

You can use a simple recursive method like this: basically, we only need to care about the previous node and current node when deleting a node.

ListNode* deleteDuplicates(struct ListNode* head) {
     deleteDuplicates(NULL, head);
     return head;
}

void deleteDuplicates(struct ListNode* pre, struct ListNode* cur) {
   if(cur == NULL)
      return;
   if(pre == NULL){
      deleteDuplicates(cur, cur->next);
   }else if(pre->val == cur->val){//Delete duplicate node
      pre->next = cur->next;
      deleteDuplicates(pre, pre ->next);
   }else{//The current node doesn't need to be deleted, move forward
      deleteDuplicates(cur, cur->next);
   }
}
share|improve this answer
    
Thank you for suggestion. There were 166 test cases. I wanted to pass all of the test cases. Consider the test case 1,2,3,3,3,4,5 : in this scenario your code will provide me with the output: 1,2,3,4,5. But instead Expected output is: 1,2,4,5 (removing all the duplicates as per the question) –  Utsav Popli Jul 30 at 9:16

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.