C++ O(1) recursive solution


  • 0
    S

    For 2 lists below,
    x1->x2->x3->x4
    y1->y2
    I want call it like (x1,null)->(x2,null)->(x3,y1)->(x4,y2).
    To realize this ,I will get length of two lists first,then we call the recursive function with longer list's head and shorter lists' as NULL,when the remain length of longer list is equal to the shorer lists length.we change NULL to shorter list's pointer.

    code is list below:

    class Solution {

    public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if(l1==NULL) return l2;
        if(l2==NULL) return l1;
        ListNode* p = l1,*retHead;
        int nLen1 = 0,nLen2 = 0 ,nCarry = 0;
        while(p){
            p=p->next;
            nLen1++;
        }
        p = l2;
        while(p){
            p = p->next;
            nLen2++;
        }
        if(nLen1==nLen2){
            p = addTwoNum(l1,l2,0,nCarry);
        }else if(nLen1>nLen2){
            head = l2;
            p = addTwoNum(l1,NULL,nLen1-nLen2,nCarry);
        }else{
            head = l1;
            p = addTwoNum(l2,NULL,nLen2-nLen1,nCarry);
        }
        if(nCarry){
            retHead = new ListNode(1);
            retHead->next = p;
        }else retHead = p;
        return retHead;
    }
    

    private:

    ListNode* addTwoNum(ListNode* l1, ListNode* l2,int nCnt,int& nCarry) {
        ListNode* retHead,*curNode;
        int nSum;
        if(l1==NULL) return NULL;
        if(nCnt>0){
            
            curNode = addTwoNum(l1->next,l2,--nCnt,nCarry);
            nSum = l1->val+nCarry;
            retHead = new ListNode(nSum%10);
            retHead->next = curNode;
            nCarry = nSum/10;
            
        }else{
            if(l2==NULL) l2 = head;
    
            curNode = addTwoNum(l1->next,l2->next,0,nCarry);
            nSum = l1->val+l2->val+nCarry;
            retHead = new ListNode(nSum%10);
            retHead->next = curNode;
            nCarry = nSum/10;
        }
        return retHead;
    }
    ListNode* head = NULL;
    

    };

    ListNode* head = NULL;
    

    };


  • 0
    S
    This post is deleted!

  • 0
    S
    This post is deleted!

Log in to reply
 

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