Home | Projects | Notes > Problem Solving > LC - E - 2. Add Two Numbers

LC - E - 2. Add Two Numbers

Solutions in C++

Solution 1

When adding two one-digit numbers:

• Sum without carry: sum % 10

• Carry: sum / 10

Complexity Analysis:

• $T=O(n)$$T=O(n)$

• $S=O(1)$$S=O(1)$ where $n$$n$ is the number of elements in the longer list of the two

Solution:

xxxxxxxxxx
40
1
// Definition for singly-linked list.
2
// struct ListNode {
3
//     int val;
4
//     ListNode *next;
5
//     ListNode() : val(0), next(nullptr) {}
6
//     ListNode(int x) : val(x), next(nullptr) {}
7
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
8
// };
9

10
class Solution {
11
public:
12
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
13
        ListNode dummy(0), *curr;     // create dummy node statically to prevent
14
                                      // memory leak
15
        curr = &dummy;
16
        int carry = 0;
17
        
18
        while (l1 || l2 || carry)
19
        {
20
            if (l1)
21
            {
22
                carry += l1->val;
23
                l1 = l1->next;
24
            }
25
            
26
            if (l2)
27
            {
28
                carry += l2->val;
29
                l2 = l2->next;
30
            }
31
            
32
            curr->next = new ListNode(carry % 10);    // sum without carry
33
            curr = curr->next;
34
            carry /= 10;                              // carry
35
        }
36
        
37
        return dummy.next;    // statically created dummy node will get destroyed
38
                              // automatically as soon as this function terminates
39
    }
40
};

Solution 2

My first solution. There are lots of redundancies in the code which could have been eliminated by using a dummy node as is described in the Solution 1.

Complexity Analysis:

• $T=O(n)$$T=O(n)$

• $S=O(1)$$S=O(1)$ where $n$$n$ is the number of elements in the longer list of the two

Solution:

xxxxxxxxxx
69
1
// Definition for singly-linked list.
2
// struct ListNode {
3
//     int val;
4
//     ListNode *next;
5
//     ListNode() : val(0), next(nullptr) {}
6
//     ListNode(int x) : val(x), next(nullptr) {}
7
//     ListNode(int x, ListNode *next) : val(x), next(next) {}
8
// };
9

10
class Solution {
11
public:
12
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
13
        int carry = false;
14
        int temp = 0;
15
        
16
        if ((temp = l1->val + l2->val + carry) >= 10) 
17
        {
18
            carry = true;
19
            temp %= 10;
20
        }
21

22
        else
23
        {
24
            carry = false;
25
        }
26

27
        ListNode *l = new ListNode(temp);
28
        ListNode *ptr = l;
29
        l1 = l1->next;
30
        l2 = l2->next;
31
        
32
        while (l1 || l2)
33
        {
34
            temp = 0;
35
            
36
            if (l1)
37
            {
38
                temp += l1->val;
39
                l1 = l1->next;                
40
            }
41
            if (l2)
42
            {
43
                temp += l2->val;
44
                l2 = l2->next;
45
            }
46
            if ((temp += carry) >= 10)
47
            {
48
                carry = true;
49
                temp %= 10;
50
            }
51
            else
52
                carry = false;
53
            
54
            ptr->next = new ListNode(temp);
55
            ptr = ptr->next;
56
            
57
        }
58
        
59
        if (carry)
60
        {
61
            ptr->next = new ListNode(1);
62
            ptr = ptr->next;
63
        }
64
        
65
        ptr->next = nullptr;
66

67
        return l;
68
    }
69
};

Solution 3

This solution uses recursion. One drawback of this solution is that if the size of two lists differ, extra memory consumption occurs to create nodes dynamically. Just note the idea of applying recursion.

Complexity Analysis:

• $T=O(n)$$T=O(n)$

• $S=O(?)$$S=O(?)$ where $n$$n$ is the number of elements in the longer list of the two

Solution:

xxxxxxxxxx
24
1
class Solution {
2
public:
3
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
4
       return addByDigit(l1, l2, 0);
5
    }
6
    
7
    ListNode *addByDigit(ListNode *l1, ListNode* l2, int carry)
8
    {
9
        // create dummy nodes dynamically if necessary
10
        if (l1 == nullptr) l1 = new ListNode(0);
11
        if (l2 == nullptr) l2 = new ListNode(0);
12
        
13
        // create a node that contains the sum of two digits
14
        ListNode *l = new ListNode((l1->val + l2->val + carry) % 10);
15
        carry = (l1->val + l2->val + carry) / 10;
16
        
17
        // recursive call
18
        if (l1->next || l2->next || carry)
19
            l->next = addByDigit(l1->next, l2->next, carry);
20
        
21
        // base case
22
        return l;
23
    }
24
};