## Add Two Numbers II

• Time:O(m + n), where m = |\texttt{l1}| and n = |\texttt{l2}|
• Space:O(m + n)

## C++

``````class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<ListNode*> stack1;
stack<ListNode*> stack2;

while (l1) {
stack1.push(l1);
l1 = l1->next;
}

while (l2) {
stack2.push(l2);
l2 = l2->next;
}

ListNode* head = nullptr;
int carry = 0;

while (carry || !stack1.empty() || !stack2.empty()) {
if (!stack1.empty())
carry += stack1.top()->val, stack1.pop();
if (!stack2.empty())
carry += stack2.top()->val, stack2.pop();
ListNode* node = new ListNode(carry % 10);
carry /= 10;
}

}
};
``````

## JAVA

``````class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Deque<ListNode> stack1 = new ArrayDeque<>();
Deque<ListNode> stack2 = new ArrayDeque<>();

while (l1 != null) {
stack1.push(l1);
l1 = l1.next;
}

while (l2 != null) {
stack2.push(l2);
l2 = l2.next;
}

ListNode head = null;
int carry = 0;

while (carry > 0 || !stack1.isEmpty() || !stack2.isEmpty()) {
if (!stack1.isEmpty())
carry += stack1.pop().val;
if (!stack2.isEmpty())
carry += stack2.pop().val;
ListNode node = new ListNode(carry % 10);
carry /= 10;
}

}
}
``````

## Python

``````class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
stack1 = []
stack2 = []

while l1:
stack1.append(l1)
l1 = l1.next

while l2:
stack2.append(l2)
l2 = l2.next

carry = 0

while carry or stack1 or stack2:
if stack1:
carry += stack1.pop().val
if stack2:
carry += stack2.pop().val
node = ListNode(carry % 10)