Most optimal way to find the sum of 2 numbers represented as linked lists

Solution 1:

1. reverse list-1
2. reverse list-2
3. find the sum and store it in a new list represented by list-3
4. reverse the list.

The complexity of this should be of the O(n+m). Is there anyway to reduce it, or do it better????

Solution2 :

You can do better without list reversal. WLOG(Without loss of generality) I'll assume that both lists h of equal length (prepend with 0 if necessary).

Start the addition from left right (from most significant to least significantple digit). You have 3cases, depending of the sum two digits:

1. = 9 : keep the nine and increase a counter
2. <>counter x nine, write sum, reset counter
3. > 9 : increase last digit, write counter x zero, write sum (modulo 10), reset counter

I'll work on the following example:



2 568 794 +
1 438 204
--------- =
4 006 998

Add 2 + 1 = 3: case 3.
list = (3), counter = 0
Add 5 + 4 = 9: case 1
list = (3), counter = 1
Add 6 + 3 = 9: case 1
list = (3), counter = 2
Add 8 + 8 = 16: case 3
list = (4, 0, 0, 6), counter = 0
Add 7 + 2 = 9: case 1
list = (4, 0, 0, 6), counter = 1
Add 9 + 0 = 9: case 1
list = (4, 0, 0, 6), counter = 2
Add 4 + 4 = 8: case 2
list = (4, 0, 0, 6, 9, 9, 8), counter = 0
 
Hope this will help to understand :)