Recursive C - No reverse/ just pure recursion - 29ms


  • 0
    A

    Simple C solution with recursion with no reverse of original lists.
    Just add few zeroes to the smallest of the two Lists (addition of zeroes can be omitted, by traversing for 'Diff', on the larger list and then start traversing on both together).
    Then recursively go to the last elements on both lists and add them, create a Linked List node, return the carry (-1 if roots are NULL), point the static newHead to this node, and go back on the call stack.

    After all nodes are calculated and carry is zero, return newHead.

    typedef struct ListNode node;
    static node *newHead;
    
    int nodeHelper(node *r1, node *r2){
        if(r1==NULL && r2==NULL) return -1;
        int carry = nodeHelper(r1->next, r2->next);
        node *temp = (node*)malloc(sizeof(node));
        int sum =(r1->val)+ (r2->val) + ((carry==-1)?0:carry);
        temp->next=(carry==-1)?NULL:newHead;
        carry = sum/10;
        sum= sum%10;
        temp->val = sum;
        newHead=temp;
        return carry;            
    }
    
    void swap(node **r1, node **r2){
        node *temp = *r1;
        *r1 = *r2;
        *r2 = temp;
    }
    
    node* mainAdder(node* r1, int lm1, node* r2, int lm2){
        int diff = abs(lm1-lm2);\
        if(lm2<lm1) swap(&r1,&r2);
        while(diff){
            node* temp = (node*)malloc(sizeof(node));
            temp->val=0;
            temp->next = r1;
            r1=temp;
            diff--;
        }
        
        int carry = nodeHelper(r1, r2);
        if(carry){
            node *temp = (node*)malloc(sizeof(node));
            temp->val = carry;
            temp->next = newHead;
            newHead=temp;
        }
        return newHead;
        
    }
    
    struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
        node *temp1= l1, *temp2=l2;
        int len1=0, len2=0;
        while(temp1){
            temp1=temp1->next;
            len1++;
        }
        while(temp2){
            temp2=temp2->next;
            len2++;
        }
        return mainAdder(l1, len1, l2, len2);
    }
    

Log in to reply
 

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