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 contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Time and Space Complexity To Target

Each list should be parsed at least once, hence the best time complexity we could have is \mathcal{O}(N_1 + N_2)O(N1​+N2​), where N_1N1​ and N_2N2​ are the numbers of elements in the lists.

Space complexity is more interesting. It’s relatively standard for linked list problems not to allocate any data structure but the output list. This way, one could target \mathcal{O}(1)O(1) space complexity without taking the output list into account.

How to Solve: Reverse Input vs. Reverse Output

The standard textbook addition algorithm begins by summing the least-significant digits. Each digit is in the range from 0 to 9, and the “overflows” are managed by moving the carry into the next range.

Algorithm

• Implement reverseList function.
• Reverse both input lists: l1 = reverseList(l1), l2 = reverseList(l2).
• Initialize the result list: head = None.
• Initialize the carry: carry = 0.
• Loop through lists l1 and l2 until you reach both ends.
• Set x1 = l1.val if l1 is not finished yet, and x1 = 0 otherwise.
• Set x2 = l2.val if l2 is not finished yet, and x2 = 0 otherwise.
• Compute the current value: val = (carry + x1 + x2) % 10, and the current carry: carry = (carry + x1 + x2) / 10.
• Update the result by adding the current value to front.
• Move to the next elements in the lists.
• If the carry is not equal to zero, append it to frond of the result list.
• Return the result list: return head.

Implementation

Complexity Analysis

• Time complexity: O(N1​+N2​), where N1​+N2​ is a number of elements in both lists.
• Space complexity: O(1) space complexity without taking the output list into account, and O(max(N1​,N2​)) to store the output list.

Implementation using Two Stacks

First we need to start from lower digit, so for that list need to be reversed. We use stack for this (separate for each list).
Then we start pushing element from both stacks at the same time, add them and form the current node of the resulting list. Two catches here:

1. we need to return the list in reversed order, similar to the input list. For that we add every “current” node as next to the list we already have. This way to form the result from tail.
2. We need to take care of carry over in case sum of digits is greater than 9. For that we keep the carry on on each step, add it to the sum and calculate new one. After both numbers are exhausted we need to check if carry on is > 0 and add one more node for it if needed.

O(max(len(l1), len(l2))) for time and space- ruled by max number of digits in list, we need to make this much iterations and allocate this much space in stack.