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;
        }
    };
    

  • 0
    F

    For future reference, a recursive solution cannot be O(1) because each call takes up room on the stack


Log in to reply
 

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