Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

445. Add Two Numbers II

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

Space: $O(m + n)$

			


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);
      node->next = head;
      head = node;
      carry /= 10;
    }

    return head;
  }
};




			


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);
      node.next = head;
      head = node;
      carry /= 10;
    }

    return head;
  }
}




			


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