Description:
https://leetcode.com/problems/add-two-numbers/#/description
Boundary:
When one is NULL while the other is not
Algorithm:
Initially, I want to implement list2int and int2lis, however, I find that when the number gets overflow, it will get the wrong result for list2int.
Therefore, the problem should be finished as done for full adder.
When (l1 != NULL && l2 != NULL)
sum = l1 -> val+ l2 -> val + carry;
when (one is NULL and the other not)
sum = (l1 or l2) -> val + carry;
finally, if (carry), add carry to the end of list.
Code:
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carry = 0;
ListNode* tmp;
ListNode *start = NULL;
ListNode *node = start;
int n1, n2, sum;
while (l1 != NULL || l2 != NULL)
{
if (l1 == NULL)
{
n1 = 0;
}
else
{
n1 = l1->val;
l1 = l1->next;
}
if (l2 == NULL)
{
n2 = 0;
}
else
{
n2 = l2->val;
l2 = l2->next;
}
sum = n1 + n2 + carry;
carry = sum / 10;
if (start == NULL)
{
start = new ListNode(sum % 10);
node = start;
}
else
{
tmp = new ListNode(sum % 10);
node->next = tmp;
node = tmp;
}
}
if (carry)
{
tmp = new ListNode(carry);
node->next = tmp;
}
return start;
}
};
Tip:
My code is identical to the example code of the fastest. However, the fastest is 26ms while mine is 55ms! Why???