Refer here for both recursive and iterative solution in O(1) extra space and O(n) time.


  • 0
    N
    
    // recursive
    ListNode *removedup(ListNode *head)
    {
        if(!head or !head->next) return head;
        auto node = head->next;
        int p = 0;
        while(node and node->val==head->val){
            p = 1;
            node = node->next;
        }
        if(!p){
            head->next = removedup(node);
            return head;
        }else{
            return removedup(node);   
        }
    }
    
    // iterative
    ListNode *removeiter(ListNode *head)
    {
        ListNode *temp = head;
        ListNode *make_list=NULL,*nxt = NULL;
        while(temp){
            ListNode *curr = temp->next;
            int p = 0;
            while(curr and temp->val==curr->val){
                curr = curr->next;
                p = 1;
            }
            if(!p){
                if(!make_list){
                    make_list = temp;
                    nxt = temp;
                }else{
                    nxt->next = temp;
                    nxt = nxt->next;
                }
            }
            temp = curr;
        }
        if(nxt)
            nxt->next = NULL;
        return make_list;
    }
    
    

Log in to reply
 

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