# 445 Add Two Numbers II

You are given two non-empty linked lists representing two non-negative integers. 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.
Follow up: 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
The Idea: Reverse both lists. Then set them to be equal in size by appending 0s to the smaller list. Then sum both lists element by element by using a carry. Create this list along the way. Finally, append the carry at the end assuming it is not zero.
Complexity: O(N) time and space, both of which have heavy constants (would not recommend this implementation).
pair<int, ListNode*> reverse_list(ListNode *&l) {
ListNode *iter_front = l, *iter_back = l, *prev_back = nullptr;
stack<ListNode*> s_rev;
int size = 0;
while (iter_back) {
s_rev.push(iter_back);
prev_back = iter_back;
iter_back = iter_back->next;
size++;
}
int swap_half = s_rev.size() / 2;
while (swap_half) {
swap(iter_front->val, s_rev.top()->val);
--swap_half; s_rev.pop();
iter_front = iter_front->next;
}
return {size, prev_back };
}
void make_same_size(pair<int, ListNode*> size_end1, pair<int, ListNode*> size_end2) {
int diff = size_end1.first - size_end2.first;
while (diff > 0) {
ListNode *node = new ListNode(0);
size_end2.second->next = node;
size_end2.second = node;
--diff;
}
while (diff < 0) {
ListNode *node = new ListNode(0);
size_end1.second->next = node;
size_end1.second = node;
++diff;
}
assert(diff == 0);
}
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
pair<int, ListNode*> l1_s = reverse_list(l1);
pair<int, ListNode*> l2_s = reverse_list(l2);
make_same_size(l1_s, l2_s);
int carry = 0;
while (l1) { // both are equal in size
int i_s1 = l1->val; l1 = l1->next;
int i_s2 = l2->val; l2 = l2->next;
int sum = i_s1 + i_s2 + carry;
int digit = sum % 10;
carry = sum / 10;
ListNode *node = new ListNode(digit);
iter->next = node;
iter = node;
}
else {
}
}
if (carry) {
ListNode *node = new ListNode(carry);
iter->next = node;
}
}
Testing
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
int main() {
iter->next = new ListNode(2);
iter = iter->next;
iter->next = new ListNode(4);
iter = iter->next;
iter->next = new ListNode(3);
iter = iter->next;
iter->next = new ListNode(6);
iter = iter->next;
iter->next = new ListNode(4);
iter = iter->next;
}
Simplified Python Implementation:
Convert to stack. Add the stacks together as you pop. Maintain a carry. Add the remainder of a an unfinished stack. Rebuild the linked list from the answer stack.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def ll_to_stack(self, ll):
s = []
while ll:
s.append(ll.val)
ll = ll.next
return s
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
s1 = self.ll_to_stack(l1)
s2 = self.ll_to_stack(l2)
ans = []
carry = 0
while s1 and s2:
sum = s1[-1] + s2[-1] + carry
s1.pop()
s2.pop()
if sum >= 10:
carry = 1
digit = sum % 10
ans.append(digit)
else:
carry = 0
ans.append(sum)
while s1:
sum = s1[-1] + carry
s1.pop()
if sum >= 10:
carry = 1
digit = sum % 10
ans.append(digit)
else:
carry = 0
ans.append(sum)
while s2:
sum = s2[-1] + carry
s2.pop()
if sum >= 10:
carry = 1
digit = sum % 10
ans.append(digit)
else:
carry = 0
ans.append(sum)
if carry:
ans.append(carry)
# build ll from stack