Coding Challenge: Add Two Numbers
This question is another medium difficulty interview question from LeetCode, which is related to my previous questions on Linked Lists. I think you will find the directions are simple and essentially we just have to add two numbers.
The Problem
You can find the problem here. 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 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.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
Starter Code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
}
};
Initial Thoughts
Why would we do this? I mean as software developers why would someone store a number in such a manner? Well, it turns out that strings and Linked Lists are just two options we have for storing and manipulating very large numbers.
If you think about it, a numerical value is limited to the number of bits that we can use to store it. If we use a data structure such as a Linked List, then we can make numbers that are trillions of digits in length!
The directions are fairly simple. We just have to add the numbers as we go and carry any relevant digits. This means that we need to keep track of our numbers, carry values, (which will only happen if the value is over 9) and write the value to a new Linked List object one node at a time. Remember that we must return the head node of our result Linked List data structure, which means that we need two nodes, a head node for the return Linked List and a write node which will actually append numbers.
If you are in an interview, then you may want to ask some clarifying questions. For instance, what if the numbers are of uneven length?
Input: (2->4->3->1) + (5->6->4)
Output: (7->0->8->1)
This means that we must be adding to 0 if the node of a given list has terminated as a nullptr.
If we step through numbers from examples in the problem, then we can outline an approximate solution.
- Make an int value for the value from node A and another for the value from node B. If the node is a nullptr its value should be 0.
- Add the numbers in a new int value (cVal).
- If we are carrying from before then we need to increment cVal by 1.
- If our cVal is again 10 or greater then we need to subtract 10 and indicate that we will carry a digit again next round.
- Write cVal to a new node and append that node to the return list.
- Continue until our lists end in nullptr.
A Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// this is our result node...
ListNode* resultHeadNode = nullptr;
ListNode* resultWriteNode = nullptr;
// use this to increment through the input nodes...
ListNode* currentNodeA = l1;
ListNode* currentNodeB = l2;
// use this to determine if we are carrying a value...
bool isCarrying = false;
// loop through the lists...
while((currentNodeA != nullptr) ||
(currentNodeB != nullptr) ||
(isCarrying == true))
{
int aVal = 0;
int bVal = 0;
int cVal = 0;
if (currentNodeA != nullptr)
{
// write a value...
aVal = currentNodeA->val;
// increment pointer
currentNodeA = currentNodeA->next;
}
if (currentNodeB != nullptr)
{
// write a value...
bVal = currentNodeB->val;
// increment pointer
currentNodeB = currentNodeB->next;
}
// add values...
cVal = aVal + bVal;
// are we carrying any values?
if (isCarrying) {
// add a 1 for the carry digit...
cVal++;
isCarrying = false;
}
// this procedure if we need to carry values further...
if (cVal > 9) {
isCarrying = true;
cVal-=10;
}
// make a new node...
ListNode* newNode = new ListNode(cVal);
if (resultWriteNode == nullptr)
{
// write value to head...
resultHeadNode = newNode;
}
else
{
// write new node to write node...
resultWriteNode->next = newNode;
}
// increment write node...
resultWriteNode = newNode;
}
return resultHeadNode;
}
};
Asymptotic Analysis
This solution runs in O(n) time and returns a data structure of O(n) space. If you do not factor in the size of the returned data structure then the space complexity is a constant O(1). I say 'if' because I have had interviews where not all data structures created, including the solution, contribute to the space complexity. I try to be precise in my articles but let me tell you that I can sometimes be wrong in my analysis.
Conclusion
Linked List questions are occasionally complicated. However, I want you to think of many of them as an exercise. Do you know how to iterate through a Linked List? Do you know how to link a new node to your Linked List? These are the two important questions to understand in an interview, regardless of the language. I hope this code solution above was commented well enough and that it makes sense. There are a few key Linked List exercises that I want to publish in my blog. Until next time:
Be good to each other and take it easy...
-Will ?(?ヮ??)