# 445. Add Two Numbers II

• Time: $O(m + n)$, where $m = |\texttt{l1}|$ and $n = |\texttt{l2}|$
• Space: $O(m + n)$
  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 class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { stack stack1; stack 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); node->next = head; head = node; carry /= 10; } return head; } }; 
  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 class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Deque stack1 = new ArrayDeque<>(); Deque 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); node.next = head; head = node; carry /= 10; } return head; } } 
  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 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 head = None carry = 0 while carry or stack1 or stack2: if stack1: carry += stack1.pop().val if stack2: carry += stack2.pop().val node = ListNode(carry % 10) node.next = head head = node carry //= 10 return head