How do you add two numbers that are stored as linked lists in reverse order, and what are the tricky cases?
You add the numbers from the end of the lists, because in a list that is stored backwards the last digit is the first node. And you carry the extra ten into the next pair.
So how do you do it? You keep a carry that starts at zero. At each step you add the two digits and the carry, and the result digit is that sum taken modulo ten, and the new carry is that sum divided by ten and rounded down.
the digits the sum the result digit the new carry
----------- -------- ---------------- --------------
5 and 7 12 2 1
3 and 9 12 2 1
4 and 6 11 1 1
And what are the tricky cases? There are three.
The first one is when the lists are different lengths. The number 342 is stored as 2, 4, 3 and the number 65 is stored as 5, 6. After two rounds the second list runs out, and from then on you just carry the first list's digits plus the carry.
The second one is when there is a carry left at the end. For example 9 plus 1 gives a result that starts with a new digit, so you have to add one more node at the front.
The third one is when one of the lists is empty from the start. Then the answer is just the other list, though usually you copy it rather than sharing the nodes.
And there is a fourth case that the question usually mentions. If the numbers were stored forwards, with the most important digit first, then you would have to use a stack or reverse the lists first, because you can only add from the end. That is a separate question and it is a good one to ask about in an interview, because it shows that you noticed the difference.
the number 342 is stored as 2 -> 4 -> 3
the number 465 is stored as 5 -> 6 -> 4
the answer 807 is stored as 7 -> 0 -> 8
So the rule to remember is this. Add from the end of the list, keep a carry, and the answer is built backwards.
The last question in this topic shows the code.