Leetcode

Add Two Numbers II

May 26, 2022 by aAshish

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

    return head;
  }
};

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

    return head;
  }
}

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

    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