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
ands2
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
andl2
), 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 variablecarry
is initialized to0
. -
Add Numbers:
-
While there are still values in either
s1
ors2
, or there is a nonzerocarry
, we continue to process the addition. -
We pop values from
s1
ands2
respectively (if available, or default to0
) and add them together along with thecarry
. -
The sum is split using
divmod(s, 10)
, wheresum = s
is the result of the addition, anddivmod()
returns a tuple(carry, val)
. Here,carry
is the amount to be carried to the next most significant digit, andval
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 atdummy.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 EvaluatorExample 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
ands2
. -
Populate Stacks: We traverse
l1
and push each digit ontos1
, and do the same withl2
tos2
. After this,s1
holds the sequence2, 4, 3
ands2
holds5, 6, 4
.1s1: [3, 4, 2] 2s2: [4, 6, 5]
-
Prepare for Addition: Create a dummy node
dummy
and setcarry
to0
. -
Add Numbers: The steps within the loop:
-
Pop
s1
(3) ands2
(4), add them withcarry
(0) giving us 3 + 4 + 0 = 7. Setcarry
to 0, and the digit to add is 7. -
Pop
s1
(4) ands2
(6), add them withcarry
(0) giving us 4 + 6 + 0 = 10. Setcarry
to 1 (divmod(10, 10)), and the digit to add is 0. -
Pop
s1
(2) ands2
(5), add them withcarry
(1) giving us 2 + 5 + 1 = 8. Setcarry
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
.
- 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
-
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 andO(m)
for l2, wheren
is the number of nodes in l1 andm
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.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.