A Simple C Solution in O(n) time


  • 0
    H

    The concept of doing solving the question is we marking a flag if a node is present more than one time.Now if a node is present more than one time than we have to delete the node except.
    So what we are going to do is we delete all the duplicate nodes of a nodes except one and mark flag as 1.Now we have to delete the last one node: For this we will delete the current node by using three cases and mark flag as 0.And when a node's value is note equal to it's next node's val then simply move to the next position and again check for the same.

    struct ListNode* deleteDuplicates(struct ListNode* head) {
        
            struct ListNode *curr,*next;
            int flag=0;
        
            curr=head;
            while(curr!=NULL)
            {
                if(curr->next!=NULL && curr->val==curr->next->val)
                {
                    struct ListNode *temp=curr->next;
                    curr->next=temp->next;
                    free(temp);
                    flag=1;
                    
                }
                else if(flag==1)
                {
                    if(curr==head)
                    {
                         struct ListNode *temp=curr;
                         head=head->next;
                         free(temp);
                    }
                    else if(curr->next!=NULL)
                    {
                        curr->val=curr->next->val;
                        struct ListNode *temp=curr->next;
                        curr->next=temp->next;
                        free(temp);
                    }
                    else
                    {
                        struct ListNode *ptr=head;
                        for(;ptr->next->next!=NULL;ptr=ptr->next);
                          
                        struct ListNode *temp=ptr->next;
                        ptr->next=NULL;
                        free(temp);
                        
                    }
                    
                    flag=0;
                }
                else
                {
                    curr=curr->next;
                }
                
                
            }
        
        
        return head;
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.