Leet Code: Add Two Numbers
y
Author: Jason Smith
Greetings programs!
The LeetCode problem we will be tackling in this post is Add Two Numbers. It is classified as a medium problem. With this problem the key things you needed to know were how to traverse a Linked List and to keep track of your carry over value.
Problem Description
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.
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
Each node in the arrays is a column of the number for that array. So the first node is the ones column, the second node is the tens column, the third is the hundreds, and so on. So just like doing this by hand on paper we just need to add the numbers up and carry over the overflow to the next column.
To solve this one I traversed the two linked lists at the same time and one by one added the values together. Then I created a new node for my answer list. The important step to remember is that you need to keep your answer between the values of 0 and 9. To do that I created a carry variable that will hold how many 10's I need to pass on as 1's to the next column of our number.
Finally the last thing I needed to check was if there was any carry over left at the end. If there was carry over left then I created a new node with that value and added it to the end of my answer list.
This solution was a simple iterative approach that only required looping through the arrays once. So it has a O(N) runtime. Since we return a LinkedList that is the same size as our array, this also has an O(N) memory usage.
Conclusion
Overall the difficulty in this problem for me came more from Rust than it did the problem itself. Had this been handled in C I could have just created pointers and traversed the list easily, but in Rust we have the awkward as_deref() that we have to do to appease the borrow checker. It's not difficult and it makes sense, but that was the only real difficult part of this problem.
There is a video of me solving this problem as well.
End of Line