Recursive, O(1) space, simple C++ solution


  • 0
    O
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            
            int length1 = length(l1);
            int length2 = length(l2);
                    
            ListNode *res;
            int carry = 0;
            if (length1 >= length2)
            {
                carry = add(l1, l2, (length1-length2));
                res = l1;
            }
            else
            {
                carry = add(l2, l1, (length2-length1));
                res = l2;
            }       
            
            if (carry)
            {
                ListNode *tmp = new ListNode(1);
                tmp->next = res;
                res = tmp;
            }
            
            return res;
        }
        
        // Adds the linked lists
        int add(ListNode *bigger, ListNode *smaller, int diff)
        {
            if (bigger == NULL)
            {
                return 0;            
            }
            
            int carry, num;
            if (diff > 0)
            {
                carry = add(bigger->next, smaller, diff-1);
                num = carry + bigger->val;
            }
            else
            {
                carry = add(bigger->next, smaller->next, 0);
                num = carry + bigger->val + smaller->val;
            }
        
            bigger->val = num % 10;
            
            return num / 10;
        }
        
        // Calculates length
        int length(ListNode* l1)
        {
            return (l1 == NULL) ? 0 : length(l1->next)+1;
        }
    };
    

Log in to reply
 

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