LeetCode: Add Two Numbers With TypeScript
Oct 9, 2022 · 3 min readIn this post, we’ll be solving “Add Two Numbers” from LeetCode.
The title sounds so simple but it’s actually much more challenging then it sounds because we’re dealing with linked list.
A linked list is a sequence of nodes that contain two fields: an integer value and a link to the next node.
Now, let’s go and solve the problem!
Problem
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, 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:
Example 2:
Example 3:
Constraints:
- The number of nodes in each linked list is in the range
[1, 100]
. 0 <= Node.val <= 9
- It is guaranteed that the list represents a number that does not have leading zeros.
Solution
Analysis
This is a simple addition problem.
But in the linked list version, the numbers are sorted in reverse. That means we have to do our addition in reverse too.
Approach
- Create a dummy list node that’ll point to our answer (This value should never change).
- Create a cursor that’ll manage our answer’s linked list.
- Traverse both list, but when the list is
null
, we replace the value with0
. Just like in real world addition (no number is equal to 0). - When traversing through the list, we add the number normally while also keeping track of the
carry
. - After the addition is performed, have our cursor point to the addition result.
- Repeat until both list are traversed (both list are
null
). - There might be an extra carry after the last addition, Let’s not forget to handle that!
- Finally, return what our dummy list node from step 1 is pointing to.
Code
First, let’s look at how our linked list is constructed:
Now, for the solution:
Time Complexity
The time complexity is O(Max(m, n))
because both of the list will only be traversed once, and the complexity depends on which list is longer.
Space Complexity
The space complexity is O(1)
because we’re using space only for our variables.
Wrap Up
That’s it for LeetCode’s “Add Two Numbers” 🎉.
You can also find the code on my Github.