1
\$\begingroup\$

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;


}
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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);
   }
}
\$\endgroup\$
1
  • \$\begingroup\$ 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) \$\endgroup\$ Commented Jul 30, 2015 at 9:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.