445. Add Two Numbers II

Problem Description

In this problem, we are given two linked lists representing two non-negative integer numbers. The digits are stored in reverse order, meaning that the least significant digit is at the head of the list, and each node contains a single digit. Our goal is to add these two numbers together and return a linked list that represents the sum of these two numbers. Importantly, the most significant digit is at the front of the result linked list. Leading zeros are not present in the numbers, except in the case of the number 0 itself.

Intuition

The intuitive approach to this problem is to follow the way we normally add numbers on paper. Normally, we add numbers starting from the least significant digit and move towards the most significant digit, carrying over any overflowing value to the next digit. However, in this scenario, since the most significant digit is at the head, we need a way to process the numbers from least significant to most significant.

To accomplish this, we can use stacks for each linked list to reverse the digits. By pushing the digits on to the stacks, the last digit pushed will be the least significant, which allows us to pop from the stack to get digits in the reverse order, allowing us to add the two numbers from least to most significant digits just as we would on paper.

Once we have the two stacks, we add the digits, keeping track of the carry. Every time we pop a digit from a stack, we add it to our running sum along with the carried value from the previous addition. If the sum is greater than 9, we calculate the new carry that will be added to the next pair of digits. Else, the carry is set to zero.

The added complication compared to adding numbers directly is dealing with different lengths of the linked lists. We handle this by considering a value of 0 for a list if it has no more digits to pop.

Once we have processed both stacks, we may still have a carry left over, which should form a new digit in the result. For example, adding 95 and 7 would require a new '1' at the front after processing the two initial digits.

The solution creates the resulting list in reverse (starting with the least significant digit), using a dummy head to simplify the edge case of the leading digit. This way, we insert each new digit at the head of the resulting list. At the end, we simply need to return the list starting from the dummy head's next node, which represents the most significant digit of the result.

Learn more about Stack, Linked List and Math patterns.

Solution Approach

The solution to this problem consists of several key steps, which utilize data structures such as stacks, as well as a dummy node pattern to simplify the list construction. The algorithm proceeds as follows:

Initialize Stacks: Two stacks s1 and s2 are created to hold the digits from the two linked lists, ensuring we can process them in a least-significant to most-significant order.
Populate Stacks: We iterate through each linked list (l1 and l2), pushing the value of each node onto the respective stack. Thus, the last node's value will be at the top of the stack.
Prepare for Addition: A dummy node dummy is created to facilitate the easy addition of new nodes at the front of the result linked list. A variable carry is initialized to 0.
Add Numbers:
- While there are still values in either s1 or s2, or there is a nonzero carry, we continue to process the addition.
- We pop values from s1 and s2 respectively (if available, or default to 0) and add them together along with the carry.
- The sum is split using divmod(s, 10), where sum = s is the result of the addition, and divmod() returns a tuple (carry, val). Here, carry is the amount to be carried to the next most significant digit, and val is the value of the current digit.
Build Result List:
- For each summation step, a new node with value val is created and prepended to the linked list starting at dummy.next.
- This ensures that we are building the result list from least-significant to most-significant, starting with the dummy node, which does not contain a digit.
Return Result: After completing the iteration, we return the linked list starting from dummy.next, which skips over the dummy node to return the correct leading digit of the result.

The code makes use of standard linked list manipulation techniques, leveraging the stack data structure to reverse the processing order of digits in the linked list. By inserting nodes at the head (using the dummy node pattern), we efficiently construct the list in reverse, following our algorithm for addition. This effectively tackles the constraint that the most significant digit appears first in each input linked list.

The mathematical concepts invoked are primarily those related to simple addition and carry-over rules from elementary arithmetic. The particular use of the Python built-in function divmod() is a straightforward way to separate the value of the current digit and the carry in a single line of code, enhancing clarity and efficiency.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with a small example where we have two linked lists representing the numbers 243 and 564. The linked lists for these numbers are given in reverse order: l1 = 3 -> 4 -> 2 and l2 = 4 -> 6 -> 5.

Step-by-step process:

Initialize Stacks: Create two empty stacks, s1 and s2.
Populate Stacks: We traverse l1 and push each digit onto s1, and do the same with l2 to s2. After this, s1 holds the sequence 2, 4, 3 and s2 holds 5, 6, 4.
```
s1: [3, 4, 2]
s2: [4, 6, 5]
```
Prepare for Addition: Create a dummy node dummy and set carry to 0.
Add Numbers: The steps within the loop:
- Pop s1 (3) and s2 (4), add them with carry (0) giving us 3 + 4 + 0 = 7. Set carry to 0, and the digit to add is 7.
- Pop s1 (4) and s2 (6), add them with carry (0) giving us 4 + 6 + 0 = 10. Set carry to 1 (divmod(10, 10)), and the digit to add is 0.
- Pop s1 (2) and s2 (5), add them with carry (1) giving us 2 + 5 + 1 = 8. Set carry to 0, and the digit to add is 8.
- At this point, both stacks are empty, and carry is 0, so we end the loop.
Build Result List:
- Add nodes in front of the dummy node with the digits in the following order: 7, 0, 8. So the list after these steps would look like dummy -> 8 -> 0 -> 7.
Return Result: The final result is returned by skipping the dummy node, so we get 8 -> 0 -> 7, representing the number 807, which is the sum of 243 and 564.

Solution Implementation

1# Definition for singly-linked list.
2class ListNode:
3    def __init__(self, value=0, next_node=None):
4        self.value = value
5        self.next = next_node
6
7class Solution:
8    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
9        # Initialize stacks for the two numbers
10        stack1, stack2 = [], []
11      
12        # Push all values from the first linked list onto stack1
13        while l1:
14            stack1.append(l1.value)
15            l1 = l1.next
16      
17        # Push all values from the second linked list onto stack2
18        while l2:
19            stack2.append(l2.value)
20            l2 = l2.next
21      
22        # Initialize a dummy node to which we'll add the resulting digits
23        dummy_node = ListNode()
24
25        # Initialize carry to handle sums greater than 9
26        carry = 0
27      
28        # Iterate while there are values in either of the stacks or there is a carry value
29        while stack1 or stack2 or carry:
30            # Pop from each stack; if a stack is empty, use 0
31            sum1 = stack1.pop() if stack1 else 0
32            sum2 = stack2.pop() if stack2 else 0
33          
34            # Calculate the total sum and update carry
35            total = sum1 + sum2 + carry
36            carry, digit = divmod(total, 10)
37          
38            # Create a new node with the resulting digit and insert it at the front
39            # of the list (since we are adding numbers from the least significant digit)
40            new_node = ListNode(digit, dummy_node.next)
41            dummy_node.next = new_node
42      
43        # Return the next node after dummy node as it only serves as an anchor
44        return dummy_node.next
45

1class Solution {
2    /**
3     * Adds two numbers represented by two linked lists, where each node contains a single digit.
4     * The digits are stored in reverse order, such that the 1's digit is at the head of the list.
5     *
6     * @param l1 First linked list representing the first number.
7     * @param l2 Second linked list representing the second number.
8     * @return A linked list representing the sum of the two numbers.
9     */
10    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
11        // Stacks to store the digits of the two numbers
12        Deque<Integer> stack1 = new ArrayDeque<>();
13        Deque<Integer> stack2 = new ArrayDeque<>();
14
15        // Push all digits of l1 into stack1
16        while (l1 != null) {
17            stack1.push(l1.val);
18            l1 = l1.next;
19        }
20
21        // Push all digits of l2 into stack2
22        while (l2 != null) {
23            stack2.push(l2.val);
24            l2 = l2.next;
25        }
26
27        // 'dummyHead' is the placeholder for the result linked list 
28        ListNode dummyHead = new ListNode();
29        int carry = 0; // Initialize carry to zero
30
31        // Loop until both stacks are empty and there is no carry left
32        while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
33            // If a stack is empty, use 0 as the digit, otherwise pop the top digit
34            int sum = (stack1.isEmpty() ? 0 : stack1.pop()) + (stack2.isEmpty() ? 0 : stack2.pop()) + carry;
35          
36            // Create a new node with the sum's least significant digit and add it to the front of the linked list 'dummyHead'
37            ListNode newNode = new ListNode(sum % 10);
38            newNode.next = dummyHead.next;
39            dummyHead.next = newNode;
40
41            // Calculate the new carry value
42            carry = sum / 10;
43        }
44      
45        // Return the sum linked list, which is 'dummyHead.next' because 'dummyHead' is a dummy node
46        return dummyHead.next;
47    }
48}
49

1// Definition for singly-linked list.
2struct ListNode {
3    int val;        // Value of the node
4    ListNode *next; // Pointer to the next node
5    // Constructor to initialize with default values
6    ListNode() : val(0), next(nullptr) {}
7    // Constructor to initialize with a specific value
8    ListNode(int x) : val(x), next(nullptr) {}
9    // Constructor to initialize with a specific value and next node
10    ListNode(int x, ListNode *next) : val(x), next(next) {}
11};
12
13class Solution {
14public:
15    // Function to add two numbers represented by two linked lists
16    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
17        stack<int> stack1; // Stack to store digits of the first number
18        stack<int> stack2; // Stack to store digits of the second number
19      
20        // Push all digits of the first number onto stack1
21        for (; l1; l1 = l1->next) {
22            stack1.push(l1->val);
23        }
24        // Push all digits of the second number onto stack2
25        for (; l2; l2 = l2->next) {
26            stack2.push(l2->val);
27        }
28      
29        ListNode* dummyHead = new ListNode(); // Dummy head for the result list
30        int carry = 0; // Initialize carry to 0
31      
32        // Continue adding until both stacks are empty or there is a carry
33        while (!stack1.empty() || !stack2.empty() || carry) {
34            int sum = carry; // Start with carry over from previous iteration
35          
36            // Add the top of stack1 to sum and pop it
37            if (!stack1.empty()) {
38                sum += stack1.top();
39                stack1.pop();
40            }
41            // Add the top of stack2 to sum and pop it
42            if (!stack2.empty()) {
43                sum += stack2.top();
44                stack2.pop();
45            }
46            // Create a new node with the digit part of sum and insert it at the front
47            // Assign the created node to the next of the dummy head
48            dummyHead->next = new ListNode(sum % 10, dummyHead->next);
49            // Update carry
50            carry = sum / 10;
51        }
52      
53        // Return the next of the dummy head which points to the actual result list
54        return dummyHead->next;
55    }
56};
57

1// Definition for singly-linked list.
2type ListNode = {
3    val: number;
4    next: ListNode | null;
5    // Constructor function to create a new ListNode instance
6    new(val?: number, next?: ListNode | null): ListNode;
7};
8
9/**
10 * Sums two numbers represented by linked lists, where each node contains a single digit.
11 * The digits are stored in reverse order, such that the 1's digit is at the head of the list.
12 * @param l1 - The first linked list representing the first number.
13 * @param l2 - The second linked list representing the second number.
14 * @returns - A linked list representing the sum of the two numbers.
15 */
16function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
17    // Stacks to hold the digits of the two numbers
18    const stack1: number[] = [];
19    const stack2: number[] = [];
20
21    // Build up the stacks with the digits from the linked lists
22    while (l1) {
23        stack1.push(l1.val);
24        l1 = l1.next;
25    }
26    while (l2) {
27        stack2.push(l2.val);
28        l2 = l2.next;
29    }
30
31    // A dummy head for the result linked list
32    let resultHead = new ListNode();
33
34    // Variable to keep track of the carry
35    let carry = 0;
36
37    // Process the stacks until they are empty or there is a carry left
38    while (stack1.length > 0 || stack2.length > 0 || carry > 0) {
39        // Calculate the sum of the topmost elements and the carry
40        const sum = (stack1.pop() ?? 0) + (stack2.pop() ?? 0) + carry;
41
42        // Create a new node with the digit part of the sum
43        resultHead.next = new ListNode(sum % 10, resultHead.next);
44
45        // Update the carry for the next iteration
46        carry = Math.floor(sum / 10);
47    }
48
49    // Return the result linked list, discarding the dummy head
50    return resultHead.next;
51}
52

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by several factors:

The time it takes to iterate through the two linked lists (l1 and l2) to build the stacks s1 and s2. Since we're traversing each list once, the time complexity for this part is O(n) for l1 and O(m) for l2, where n is the number of nodes in l1 and m is the number of nodes in l2.
The time it takes to pop elements from the stacks s1 and s2 and to add the carry if it exists. In the worst case, we'll pop each element once from both stacks, which gives us another O(n + m) operations.

As the two stages are sequential, we can add these complexities together, which results in a total time complexity of O(n + m).

Space Complexity

The space complexity is determined by the additional space we need aside from the input lists:

We're creating two stacks s1 and s2 that can potentially contain all the elements of l1 and l2. This yields a space complexity of O(n + m).
We also create a dummy node and potentially new nodes equivalent to the total number of nodes that are in the two lists plus one additional node in case there is a carry at the last node. However, creating nodes for the resulting linked list does not add to the space complexity when considering the total space used since the output space is not considered in space complexity analysis for this problem.

As there's no recursive calls or dynamic memory allocation that exceeds the size of input lists, the space complexity of the code remains O(n + m).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know