# 445. Add Two Numbers II

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

``````Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
``````

``````class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1->val);
l1 = l1->next;
}
while (l2) {
s2.push(l2->val);
l2 = l2->next;
}
int sum = 0;
ListNode *res = new ListNode(0);
while (!s1.empty() || !s2.empty()) {
if (!s1.empty()) {sum += s1.top(); s1.pop();}
if (!s2.empty()) {sum += s2.top(); s2.pop();}
res->val = sum % 10;
ListNode *head = new ListNode(sum / 10);
sum /= 10;
}
return res->val == 0 ? res->next : res;
}
};
``````

``````class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int n1 = getLength(l1), n2 = getLength(l2);
head->next = (n1 > n2) ? helper(l1, l2, n1 - n2) : helper(l2, l1, n2 - n1);
}
}
int cnt = 0;
++cnt;
}
return cnt;
}
ListNode* helper(ListNode* l1, ListNode* l2, int diff) {
if (!l1) return NULL;
ListNode *res = (diff == 0) ? new ListNode(l1->val + l2->val) : new ListNode(l1->val);
ListNode *post = (diff == 0) ? helper(l1->next, l2->next, 0) : helper(l1->next, l2, diff - 1);
if (post && post->val > 9) {
post->val %= 10;
++res->val;
}
res->next = post;
return res;
}
};
``````

``````class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int n1 = getLength(l1), n2 = getLength(l2), diff = abs(n1 - n2);
if (n1 < n2) swap(l1, l2);
ListNode *dummy = new ListNode(0), *cur = dummy, *right = cur;
while (diff > 0) {
cur->next = new ListNode(l1->val);
if (l1->val != 9) right = cur->next;
cur = cur->next;
l1 = l1->next;
--diff;
}
while (l1) {
int val = l1->val + l2->val;
if (val > 9) {
val %= 10;
++right->val;
while (right->next) {
right->next->val = 0;
right = right->next;
}
right = cur;
}
cur->next = new ListNode(val);
if (val != 9) right = cur->next;
cur = cur->next;
l1 = l1->next;
l2 = l2->next;
}
return (dummy->val == 1) ? dummy : dummy->next;
}
int cnt = 0;
++cnt;
}
return cnt;
}
};
``````

https://discuss.leetcode.com/topic/67076/ac-follow-up-java

https://discuss.leetcode.com/topic/65279/easy-o-n-java-solution-using-stack

https://discuss.leetcode.com/topic/65306/java-o-n-recursive-solution-by-counting-the-difference-of-length/2