Add Two Numbers II with O(1) extra space using recursion.


  • 0
    M
    int getListLength(const struct ListNode *l){
        struct ListNode *pNode = l;
        int count = 0;
        
        while(pNode){
            count++;
            pNode = pNode->next;
        } 
        
        return count;
    }
    
    int addTwoNumbers_1(struct ListNode *l1,int len1,struct ListNode *l2,int len2){
        int carry = 0;
        int sum = 0;
        
        if(len1 == 0 || len2 == 0||
           l1 == NULL || l2 == NULL){
            return 0;
        }
        
        if(len1>len2){
            carry = addTwoNumbers_1(l1->next,len1-1,l2,len2);
            sum = carry + l1->val;
            l1->val = sum%10;
        }
        
        if(len1 == len2){
            carry = addTwoNumbers_1(l1->next,len1-1,l2->next,len2-1);
            sum = carry + l1->val + l2->val;
            l1->val = sum%10;
        }   
        
        if(len1<len2){
            carry = addTwoNumbers_1(l1,len1,l2->next,len2-1);
            sum = carry + l2->val;
            l2->val = sum%10;
        }
              
        carry = sum/10;
        
        return carry;
    }
    
    struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
        int len1 = 0;
        int len2 = 0;
        int carry = 0;
        struct ListNode *pNode = NULL;
        struct ListNode *head = NULL;
        
        len1 = getListLength(l1);
        len2 = getListLength(l2);
        
        if(len1>len2){
            carry = addTwoNumbers_1(l1,len1,l2,len2);
            pNode = l1;
        }
        
        if(len1<=len2){
            carry = addTwoNumbers_1(l2,len2,l1,len1);
            pNode = l2; 
        }
        
        if(carry>0){
            head = (struct ListNode *)malloc(sizeof(struct ListNode));
            head->val = carry;
            head->next = pNode;
            pNode = head;
        }
        
        return pNode;
    }
    

Log in to reply
 

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