Last updated on January 5th, 2025 at 01:10 am

Here, we see a Add Two Numbers II LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Linked-List

Companies

Bloomberg, Microsoft

Level of Question

Medium

Add Two Numbers II LeetCode Solution

1. Problem Statement

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]

2. Coding Pattern Used in Solution

The coding pattern used in the provided code is “In-place Reversal of a LinkedList”. This pattern is evident because the code involves reversing linked lists multiple times (e.g., reverseList function) to facilitate the addition of two numbers represented as linked lists. The reversal is done in-place, modifying the next pointers of the nodes.

3. Code Implementation in Different Languages

3.1 Add Two Numbers II C++

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = NULL;
        while(head) {
            ListNode* nxt = head->next;
            head->next = prev;
            prev = head;
            head = nxt;
        }
        return prev;
    }

    ListNode* Helper(ListNode* l1, ListNode* l2) {
        ListNode* dummyHead = new ListNode(0);
        ListNode* tail = dummyHead;
        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int digit1 = (l1 != nullptr) ? l1->val : 0;
            int digit2 = (l2 != nullptr) ? l2->val : 0;
            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;
            ListNode* newNode = new ListNode(digit);
            tail->next = newNode;
            tail = tail->next;
            l1 = (l1 != nullptr) ? l1->next : nullptr;
            l2 = (l2 != nullptr) ? l2->next : nullptr;
        }
        ListNode* result = dummyHead->next;
        delete dummyHead;
        return result;
    }

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode* ans = Helper(l1, l2);
        return reverseList(ans);
    }
};

3.2 Add Two Numbers II Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    public ListNode helper(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode tail = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int digit1 = (l1 != null) ? l1.val : 0;
            int digit2 = (l2 != null) ? l2.val : 0;
            int sum = digit1 + digit2 + carry;
            int digit = sum % 10;
            carry = sum / 10;
            ListNode newNode = new ListNode(digit);
            tail.next = newNode;
            tail = tail.next;
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        ListNode result = dummyHead.next;
        return result;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);
        ListNode ans = helper(l1, l2);
        return reverseList(ans);
    }
}

3.3 Add Two Numbers II JavaScript

var addTwoNumbers = function(l1, l2) {
    let stack1 = [];
    let stack2 = [];
    while(l1) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while(l2) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    let l3 = new ListNode(0);
    while(stack1.length || stack2.length) {
        let sum = 0;
        if(stack1.length) sum += stack1.pop();
        if(stack2.length) sum += stack2.pop();
        sum += l3.val;
        l3.val = sum%10;
        let head = new ListNode(Math.floor(sum/10));
        head.next = l3;
        l3 = head;
    }
    return (l3.val === 0) ? l3.next : l3;
};

3.4 Add Two Numbers II Python

class Solution(object):
    def reverseList(self, head):
        prev = None
        curr = head
        while curr:
            nxt = curr.next
            curr.next = prev
            prev = curr
            curr = nxt
        return prev

    def helper(self, l1, l2):
        dummyHead = ListNode(0)
        tail = dummyHead
        carry = 0
        while l1 or l2 or carry:
            digit1 = l1.val if l1 else 0
            digit2 = l2.val if l2 else 0
            total = digit1 + digit2 + carry
            digit = total % 10
            carry = total // 10
            newNode = ListNode(digit)
            tail.next = newNode
            tail = tail.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        result = dummyHead.next
        return result

    def addTwoNumbers(self, l1, l2):
        l1 = self.reverseList(l1)
        l2 = self.reverseList(l2)
        ans = self.helper(l1, l2)
        return self.reverseList(ans)

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	(O(n + m))	(O(n + m))
Java	(O(n + m))	(O(n + m))
JavaScript	(O(n + m))	(O(n + m))
Python	(O(n + m))	(O(n + m))

• The “In-place Reversal of a LinkedList” pattern is used in C++, Java, and Python, while JavaScript uses a stack-based approach to simulate reversal.
• The time complexity is linear because each node is processed a constant number of times.
• The space complexity is dominated by the new linked list created to store the result.