2. Add Two Numbers

發表於 | 分類於

problem

solution

option 1 - iterative

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* ret = new ListNode(-1), *ans = ret;
        int carry = 0;
        while(l1 || l2 || carry){
            int sum = carry;
            if(l1){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2){
                sum+=l2->val;
                l2=l2->next;
            }
            ret->next = new ListNode(sum%10);
            ret = ret->next;
            carry = sum/10;
        }
        return ans->next;
    }
};

option 2 - recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    ListNode* addTwo(ListNode* l1, ListNode*l2, int carry){
        if(!l1 && !l2 && carry == 0) return nullptr;
        
        ListNode * node;
        if(l1 || l2 || carry){
            int sum = carry;
            if(l1){
                sum+=l1->val;
                l1=l1->next;
            }
            if(l2){
                sum+=l2->val;
                l2=l2->next;
            }
            node = new ListNode(sum%10);
            sum/=10;
            node->next = addTwo(l1, l2, sum);
        }
        return node;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *ret = new ListNode(-1);
        ret->next = addTwo(l1, l2, 0);
        return ret->next;
    }
};

analysis

  • option 1
    • time complexity O(n)
    • space complexity O(1)
  • option 2
    • time complexity O(n)
    • space complexity O(n) function call