If you are wondering, the first post is here… I’m thinking of making this a series, so it is likely that you will see a post like this every two week or so. Maybe more frequent maybe less, depending on how hardworking I am :) I’ll probably not go into the very hard or “classic” questions where every CS student or fresh grad had tackled in their studies or first job interviews, but maybe the less common ones that pique my interest. Anyway, here’s the question I’m doing for the week...
Just another generic programming image... Photo by AltumCode on Unsplash
If you had ever been on Leetcode, you might have saw this question before, as it is literally on the first page of the questions list, and it is the second question in the list. Despite the title looks really trivial (it’s literally just “Add Two Numbers”), it is listed with a difficulty of medium. If you clicked into it and tried it for yourself, it becomes quite clear that the difficulty rating is quite well-reasoned. The question indeed wants you to add two numbers, but not with the trivial way of just using a single “+”.
The question gives you two singly linked lists, each representing one number. The representation goes like this: Each node in the linked list represents a digit of the number, starting from the least significant one. Hence, for a number “657”, it is represented with a linked list of “7 -> 5 -> 6”. The task is about needing you to add these two numbers up, and return the result in the same representation. So for example, if the question gives you “5 -> 5” and “1 -> 1”, your algorithm needs to return “6 -> 6”. Nothing too fancy, but not too direct.
I first attempted this question several years ago when I’m still a complete newbie to algorithms and programming, and it didn’t went so well. However, it had became a question I remember really well, and I can’t help but think about it every time I get randomly reminded about it. It’s probably one of the problems on the platform that I really like, for a number of reasons. The solution uses a pretty trivial approach, which isn’t hard to think of, neither is it hard to implement. But, if you don’t have the necessary knowledge on the data structures used, you’re in for a bad time. The problem also doesn’t have many edge cases to cover, which means that if your approach is correct, it will very likely go through all the tests without the need for you to add ugly if-else blocks to catch the edges. The data structure provided by Leetcode for the linked list is also quite nice to use, hence depending on the language, allowing you to tackle the problem with methods that take advantage of some features of the data structure provided. It’s in general a more fun problem to solve than the ones you can just remember a solution to and just paste it in.
Enough introduction talk, so for my approach to the problem... We first look at the non-code overview of how it can be solved.
While the input numbers for this problem sound a little unintuitive, with some imagination, you might very quickly realise that they are quite handy to work with if you treat them as numbers in vertical addition. Start from the first digit, add it with first digit in the other linked list, save the result into the result linked list, remember if there is a carry, then move on to the next digit for both linked lists, continue until you don’t have digits to add anymore from all the first linked list, second linked list and the carry.
Vertical addition, with linked list stuff...
This is indeed how the logic goes...
1. Define a variable for the solution, which is to be returned later.
2. Define a variable for the carry.
3. Calculate the sum of the digits, reduce them below 10 if required.
4. Save the sum in a node in the solution linked list variable.
5. Update the carry variable.
6. Move the two linked lists to the next node.
7. Repeat 3 to 6 until there are no more digits left from both linked lists, and there is no carry left.
That is roughly the logic to implement. But with a little difference, because, well, as usual, computers are dumb. So, we need to explicitly tell the computer to do some extra stuff, like having another variable to take note where we are in the solution linked list, a line to manually move the solution linked list to the next node before calculating the sum for the next digits, and to not move to the next digit in the linked lists if we are already at the end of the linked list (there is the case of one number being fully traversed but the other number still has digits to be taken care of, such as in the case of 10000 + 1). With these taken care of, the full code looks like this (in C#).
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
var resHead = new ListNode();
var resRef = resHead;
int carry = 0;
while (!(l1 == null && l2 == null && carry == 0)) {
int val =
(l1 == null ? 0 : l1.val) +
(l2 == null ? 0 : l2.val) +
carry;
resRef.next = new ListNode();
resRef.next.val = val % 10;
carry = val / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
resRef = resRef.next;
}
return resHead.next;
}
}
You might have noticed that instead of returning the entire result linked list, we return it from the second node onwards. This is due to that we start writing our solution into the solution linked list from its second node, as doing it from the first node would be ugly, since we will need to explicitly handle the case of when you are dealing with the first node. I tried doing it for my first few attempts, but it turned out to be uglier than I would like to debug, so let’s just do this instead, lol.
But if we look at the data structure provided by Leetcode for this question, it seems like we can solve this problem with a much cleaner algorithm, by making good use of the constructor given by Leetcode for this linked list node class, and a C# feature of optional method arguments. The class provided by Leetcode has a constructor for us to directly set the value of the node and the linked next node in it. Hence, it is possible to tackle this problem with a recursive function that recursively calls itself at the end for the value of the next node instead of needing us to use a while loop.
The node class provided by Leetcode for the question if you select to solve the problem in C#.
The only problem with this is that we will need some way to tell the next function call whether there is a carry or not. We can build two functions, one that adds an extra one to the result (for the case when there’s a carry), and another that doesn’t (for the case when there’s no carry). However, that sounds super ugly – we can do something else instead. C# allows optional arguments for methods, so we can just attach a carry argument to the provided method and pass the value of the carry in it instead. With this approach, we can use an algorithm like this:
public class Solution {
public ListNode AddTwoNumbers(ListNode l1, ListNode l2, int carry = 0) {
if (l1 == null && l2 == null && carry == 0) {
return null;
}
else {
int v1 = (l1 == null ? 0 : l1.val);
int v2 = (l2 == null ? 0 : l2.val);
int sum = v1 + v2 + carry;
return new ListNode(
sum % 10,
AddTwoNumbers(
l1 == null ? null : l1.next,
l2 == null ? null : l2.next,
sum / 10
)
);
}
}
}
It’s very short and concise, and if I don’t care about readability, this thing can just be two lines, one for the if and another for the else, with only two semicolons involved. But for the sake of good practice... let’s not do that. Compared to the version using the while loop, this version runs slightly slower, presumably due to the use of recursion. Recursion algorithms normally runs slower than their non-recursive equivalents due to the overhead of function calls, so it’s expected. Although, I don’t really trust the code running duration results, as Leetcode seems to have a problem with timing C# code running time. Last time my superior and me got vastly different results from the same code, so, as long as the system accepts it and I know that the complexity isn’t terrifying, it’s good enough for me.
Originally, the post would have ended here, but I can’t help but think of a super dumb approach to this very question. What if, we are stubborn and want to solve the addition with a good old single “+”?
It sounds doable, since it must be possible to traverse through the two linked lists to get the number they are representing, add them up, and generate a linked list from the result we got after the addition. The idea sounds very ugly and bad, but if you think of it, it still runs in O(n) time, which makes it both better and worse at the same time.
I indeed tried to implement it last time using some language like Python, but it didn’t go well, and I’m quite sure that I had done some mistakes in converting between the numbers and the linked lists or the other way round. Probably I can also do it by first getting the numbers in a string first before converting it into an integer and do the addition, then convert it back to string to convert it back to a linked list... that’s a horrifying lot of additional steps, but it does sound like an idea that would work. Nevertheless, I gave up with this terrifying idea after a little too many failed attempts (and I really only tried doing this when I’m burnt out from something else, which isn’t a good idea as well).
If anyone reading this thinks that it’s worth the time to implement this horrible idea on my behalf just to see how slow or fast it runs, go on, I’ll be waiting for your results...
...and uh, yes, until next time.
:)