Problem: Suppose you are given two non-empty linked lists representing two non-negative integers. The numbers are stored in reverse order, and each node is a single digit. Add the two numbers and return it as a linked list.
This problem is interesting due to it having a lot of moving parts. The best things to do with a problem like this is try a few examples first, so we can get an idea of what the problem is really asking, and what cases may come up.
First, let’s try the provided example:
Input 1: [2,4,3]
Input 2: [5,6,4]
You can see that in this example, our algorithm to calculate the answer is easy. We simply add each digit, keeping track of any carry that might occur. If there is a carry, we add it to the next digit. Once we reach the end of both digits, we are done. This is the easiest case of the problem, since both numbers are the same size, and carry doesn’t exceed the number of digits provided. Something slightly harder could be the following:
Input 1: [2,4,3]
Input 2: [8,0,8]
This is trickier since we end up with a number that has more digits than we started with. This is another situation we need to watch out for, if the number has carries beyond the digits calculated, we still need to consider it, otherwise our solution will be wrong. There is one final situation that we would want to consider for this problem:
Input 1: [2,2,3]
Input 2: [2,1]
In this case, we could have one number that is smaller than the other. We need to make sure that we keep track of whether we have iterated the whole of either list before we try to add a number from the list.
With these three scenarios in mind, let’s look at how we can implement a solution to this problem. To start, we are going to iterate the lists we are given until we have exhausted all the elements in both lists. To do this, we setup some tracker variables, i and j, to determine where we currently are in the list. If we have exceeded the length of either list, we simply set the current element for that list to 0 and keep adding 0 to the existing values. The loop looks like this:
The reason we are adding currSum to itself is due to how we need to track carries. Once we have added the two digits, we need to determine if the value is greater than or equal to 10. If it is, then we set currSum to 1, to indicate that there is a carry that needs to be taken care of. Once this is done, we append the currSum to our answer list, and increment i and j. Here is how the complete loop looks.
We check for a carry scenario, and mod the currentSum with 10 to reduce it to the proper digit. Once this is done, we add the carry to the sum and we are set to go. One final issue we need to take care of is carries that result in more digits than we started with. This is solved by simply placing an if statement at the end to check for carries, and add them to the end.
This is the complete algorithm for the problem, and it works for all the cases we discussed when previously looking into this problem. As a final note, let’s look at the time complexity of this solution.
In total, we iterate until all of the digits are looked at for each number provided. There could be either the same number of digits, or a different number of digits. Suppose that number one has n digits, and number two has m digits. This means that at most, we iterate Max(n,m) times. Therefore, our solution is O(Max(n,m)) time, or more generically, O(n) time, where n is the largest numbers digit count.