Leetcode 445. Add Two Numbers II

Problem Explanation

In this problem, you are given two non-empty linked lists that represent two non-negative integers. The most significant digit comes first in each list where each node has a single digit. You need to add the two numbers and return it as a linked list.

For example, the Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4); where each linked list represents a number. The first linked list represents number 7243 and the second linked list represents number 564. Adding both the numbers we get 7807. The Output will be: 7 -> 8 -> 0 -> 7.

In addition, you are asked to solve this problem without reversing the input lists or altering the input lists.

Solution Approach

To solve this problem, we will use a data structure: stacks. The reason for this choice is that a stack inherently follows the Last-In-First-Out (LIFO) rule. This rule aligns well with how we add numbers: from least significant digits (right end) towards the most significant digits (left end).

First, as we traverse through the linked lists (from left to right: the head to the end), we will push each node into the respective stacks.

After this, we initialize our head node as None and carry as 0. Then, we will pop the top node from each stack and add their values along with any carry value. Thereafter, we create a new node with our calculated value modulo 10 (to make sure we get single digit results) and then we make the new node as our new head.

In addition, we will track the carry over value (this will be our current sum divided by 10). This carry over value will be added to the stack's top values in the next iteration (if any nodes are left in the stack).

This process is repeated until we have exhausted both stacks and taken care of the carry over.

Python Solution

1
2python
3class ListNode:
4    def __init__(self, val=0, next=None):
5        self.val = val
6        self.next = next
7
8class Solution:
9    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
10        stack1, stack2 = [], []
11        while l1:
12            stack1.append(l1.val)
13            l1 = l1.next
14        while l2:
15            stack2.append(l2.val)
16            l2 = l2.next
17        
18        carry = 0
19        head = None
20        while stack1 or stack2 or carry != 0:
21            sum = carry
22            if stack1: sum += stack1.pop()
23            if stack2: sum += stack2.pop()
24            
25            node = ListNode(sum % 10)
26            node.next = head
27            head = node
28            carry = sum // 10
29        
30        return head

Java Solution

1
2java
3public class Solution {
4    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
5        Stack<Integer> stack1 = new Stack<>();
6        Stack<Integer> stack2 = new Stack<>();
7
8        while (l1 != null) {
9            stack1.push(l1.val);
10            l1 = l1.next;
11        }
12        while (l2 != null) {
13            stack2.push(l2.val);
14            l2 = l2.next;
15        }
16
17        int carry = 0;
18        ListNode head = null;
19        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
20            int sum = carry;
21            if (!stack1.isEmpty()) sum += stack1.pop();
22            if (!stack2.isEmpty()) sum += stack2.pop();
23
24            ListNode node = new ListNode(sum % 10);
25            node.next = head;
26            head = node;
27            carry = sum / 10;
28        }
29
30        return head;
31    }
32}

With these examples you now understand the basics of adding two numbers represented by two non-empty linked lists and able to return the result as a linked list. You are also able to do this without modifying the input lists.### JavaScript Solution

1
2javascript
3class ListNode {
4    constructor(val=0, next=null) {
5        this.val = val;
6        this.next = next;
7    }
8}
9
10class Solution {
11    addTwoNumbers(l1, l2) {
12        let stack1 = [], stack2 = [];
13        while (l1) {
14            stack1.push(l1.val);
15            l1 = l1.next;
16        }
17        while (l2) {
18            stack2.push(l2.val);
19            l2 = l2.next;
20        }
21
22        let carry = 0;
23        let head = null;
24        while (stack1.length || stack2.length || carry !== 0) {
25            let sum = carry;
26            if (stack1.length) sum += stack1.pop();
27            if (stack2.length) sum += stack2.pop();
28            let node = new ListNode(sum % 10);
29            node.next = head;
30            head = node;
31            carry = Math.floor(sum / 10);
32        }
33
34        return head;
35    }
36}

In our JavaScript solution, we first initialize two empty arrays, stack1 and stack2, that will serve as our stacks. We then iterate over both linked lists, pushing the value of each node to the respective stack.

We initialize variables for carry and head (resulting linked list). We start a while loop that will continue till all arrays are empty and carry is zero. In each iteration of the loop, we pop the top element from each stack and add it to carry, and then create a new node with the value of sum modulo 10.

This process iterates until the stacks are empty and carry is zero, which means all digits have been processed. The final result is a linked list depicting the sum of the two input numbers.

With the provided solutions in Python, Java, and JavaScript, you should be able to implement this problem in your preferred programming language.