C++ solution using recursion to avoid modifying the lists


  • 0
    G
    class Solution {
    public:
        
        int GetLen(ListNode *l)
        {
            if(l == NULL)
            {
                return (0);
            }
            
            return 1 + GetLen(l->next);
        }
    
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
        {
            if(l1 == NULL)
            {
                return l2;
            }
            
            if(l2 == NULL)
            {
                return l1;
            }
            
            int L1 = GetLen(l1);
            int L2 = GetLen(l2);
            
            if(L1 < L2)
            {
                return addTwoNumbers(l2,l1);
            }
    
            ListNode *Carry = NULL;
            ListNode *NextCarry = NULL;
            
            ListNode *Result = NULL;
            ListNode **pResult = NULL;
            
            while(L1 > L2)
            {
                if(Result == NULL)
                {
                    Result = new ListNode(l1->val);
                    pResult = &Result;
                }
                else
                {
                    (*pResult)->next = new ListNode(l1->val);
                    pResult = &((*pResult)->next);
                }
                
                l1 = l1->next;
                L1--;
            }
            
            while(l1 != NULL)
            {
                if(Result == NULL)
                {
                    Result = new ListNode(l1->val + l2->val);
                    pResult = &Result;
                }
                else
                {
                    (*pResult)->next = new ListNode(l1->val + l2->val);
                    pResult = &((*pResult)->next);
                }
                
                if((*pResult)->val / 10 != 0)
                {
                    if(NextCarry == NULL)
                    {
                        Carry = new ListNode(((*pResult)->val) / 10);
                        NextCarry = Carry;
                    }
                    else
                    {
                        NextCarry->next = new ListNode(((*pResult)->val)/10);
                        NextCarry = NextCarry->next;
                    }
                    
                    (*pResult)->val %= 10;
                }
                else
                {
                    if(NextCarry != NULL)
                    {
                        NextCarry->next = new ListNode(0);
                        NextCarry = NextCarry->next;
                    }
                }
                
                l1 = l1->next;
                l2 = l2->next;
            }
            
            if(Carry != NULL)
            {
                NextCarry->next = new ListNode(0);
            }
            
            return addTwoNumbers(Result,Carry);
        }
    };

Log in to reply
 

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