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

Question

Hello,

I was trying to write a program for the problem I mentioned above, the numbers (i.e the lists) can be of unequal length, I was not able to figure out a way to do this other than the most commonly thought of approach i.e

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?

Answer 1

Ideally the first thing I would do is store the numbers in reverse digit order, so 43,712 is stored as:

2 -> 1 -> 7 -> 3 -> 4

It makes arithmetic operations much easier.

Displaying a number can be done either iteratively or more simply with a recursive algorithm. Note: all this assumes singly-linked lists.

Edit: But you've since stated you have no choice in the storage format. As such, your best bet is to reverse both the lists, do the addition and then reverse the result.

Answer 2

If you can use a doubly-linked list then you can quickly traverse to the end of each list, and then just work your way back, adding the numbers at each point and add that to a new list.

You will need to determine which list is longer, and add up based on the length of the shorter list, and then just finish summing and adding the longer list.

But, you will have some issues with the fact that the sum may go over one digit, so if that happens you will need to keep track of the overflow and add that to the next node.

Answer 3

I don't think of a better solution to the problem as stated. The root problem is that you have to process the list elements in the reverse order. In theory you could implement the algorithm recursively, avoiding the need for explicit reversal steps. But that requires O(max(m,n)) stack space, and would most likely be slower.

But I think that is really saying that you've chosen a poor representation. If you represent the numbers as doubly linked lists of int or arrays of int (with an explicit size), the complexity will be O(max(m,n)) with a smaller constant of proportionality.

Note: O(max(m,n)) and O(m+n) are both abuses of O notation. Strictly speaking, O is a defined in terms of a limit as a single variable goes to infinity. Looked at it this way, O(max(m,n)) and O(m+n) both reduce to O(m) or O(n). However, I understand what you are trying to say :-).

Answer 4

The only potential optimization, which would come at the cost of some code clarity, would be to combine the initial reversals into a single loop. You then go from O(n+m+m) to O(m+m), although the steps inside the loop are costlier.

Answer 5

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

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

1. = 9: keep the nine and increase a counter
2. < 9: write 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

1. Add 2 + 1 = 3: case 3.
   • list = (3), counter = 0
2. Add 5 + 4 = 9: case 1
   • list = (3), counter = 1
3. Add 6 + 4 = 9: case 1
   • list = (3), counter = 2
4. Add 8 + 8 = 16: case 3
   • list = (4, 0, 0, 6), counter = 0
5. Add 7 + 2 = 9: case 1
   • list = (4, 0, 0, 6), counter = 1
6. Add 9 + 0 = 9: case 1
   • list = (4, 0, 0, 6), counter = 2
7. Add 4 + 4 = 8: case 2
   • list = (4, 0, 0, 6, 9, 9, 8), counter = 0

Answer 6

can u explain it in bit detail. I am confused at first step u say 2+1 =3 so write counter x nine, write sum, reset counter so two values will be written into list but only sum is written not counter x nine. Same confusion occurs at step 3. In algo only 2 values are to be written but in the list 3 values have been written that are 0,0,6.