leetcode-cpp/0002-add-two-numbers.cpp at main · j414j/leetcode-cpp · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <stdlib.h>
#include <iostream>
using namespace std;

//  Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        int carry = 0;
        ListNode *ans = new ListNode();
        ListNode *currentNode = ans;
        ListNode *nextNode;
        while (l1 != nullptr && l2 != nullptr)
        {
            // add the numbers
            int sum;
            sum = carry + l1->val + l2->val;
            carry = sum / 10;
            sum = sum % 10;
            currentNode->val = sum;
            if (l1->next != nullptr || l2->next != nullptr)
            {
                // insert next node in ans
                nextNode = new ListNode();
                currentNode->next = nextNode;

                // move to next digit
                currentNode = nextNode;
            }
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1 != nullptr)
        {
            // add the numbers
            int sum;
            sum = carry + l1->val;
            carry = sum / 10;
            sum = sum % 10;
            currentNode->val = sum;
            if (l1->next != nullptr)
            {
                // insert next node in ans
                nextNode = new ListNode();
                currentNode->next = nextNode;

                // move to next digit
                currentNode = nextNode;
            }
            l1 = l1->next;
        }
        while (l2 != nullptr)
        {
            // add the numbers
            int sum;
            sum = carry + l2->val;
            carry = sum / 10;
            sum = sum % 10;
            currentNode->val = sum;
            if (l2->next != nullptr)
            {
                // insert next node in ans
                nextNode = new ListNode();
                currentNode->next = nextNode;

                // move to next digit
                currentNode = nextNode;
            }
            l2 = l2->next;
        }
        if (carry != 0)
        {
            nextNode = new ListNode(carry, nullptr);
            currentNode->next = nextNode;
            currentNode = nextNode;
        }
        currentNode->next = nullptr;
        return ans;
    }
};

void traverse(ListNode *lst)
{
    while (lst != nullptr)
    {
        cout << lst->val;
        lst = lst->next;
    }
}

int main()
{
    ListNode *a7 = new ListNode(9);
    ListNode *a6 = new ListNode(9, a7);
    ListNode *a5 = new ListNode(9, a6);
    ListNode *a4 = new ListNode(9, a5);
    ListNode *a3 = new ListNode(9, a4);
    ListNode *a2 = new ListNode(9, a3);
    ListNode *a1 = new ListNode(9, a2);

    ListNode *b4 = new ListNode(9);
    ListNode *b3 = new ListNode(9, b4);
    ListNode *b2 = new ListNode(9, b3);
    ListNode *b1 = new ListNode(9, b2);
    traverse((new Solution())->addTwoNumbers(a1, b1));
}