445. Add Two Numbers II LeetCode Solution

In this guide, you will get 445. Add Two Numbers II LeetCode Solution with the best time and space complexity. The solution to Add Two Numbers II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Add Two Numbers II solution in C++
Add Two Numbers II solution in Java
Add Two Numbers II solution in Python
Additional Resources

445. Add Two Numbers II LeetCode Solution image

Problem Statement of 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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [8,0,7]

Example 3:

Input: l1 = [0], l2 = [0]
Output: [0]

Constraints:

The number of nodes in each linked list is in the range [1, 100].
0 <= Node.val <= 9
It is guaranteed that the list represents a number that does not have leading zeros.

Follow up: Could you solve it without reversing the input lists?

Complexity Analysis

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

445. Add Two Numbers II LeetCode Solution in 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;
  }
};
/* code provided by PROGIEZ */

445. Add Two Numbers II LeetCode Solution in 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;
  }
}
// code provided by PROGIEZ

445. Add Two Numbers II LeetCode Solution in 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
 # code by PROGIEZ