Add two big numbers represented as linked lists without reversing the linked lists

Question

Suppose you have 2 big numbers represented as linked lists, how do you add them and store the result in a separate linked list. eg

a = 2 -> 1 -> 7 
b = 3 -> 4
result = 2 -> 5 -> 1

Can you add them without reversing the linked lists

Answer 1

Pseudocode:
Step 1. Traverse the linked lists and push the elements in two different stacks
Step 2. Pop the top elements from both the stacks
Step 3. Add the elements (+ any carry from previous additions) and store the carry in a temp variable
Step 4. Create a node with the sum and insert it into beginning of the result list

Answer 2

I think this's something beyond context but can be very performance incentive for the person who originally posted this question.

So here's a recommendation:

instead of using every node as a single digit of the number, use each node to store a large number(close to the size of integer) and if the highest possible number you chose to store in each node be x(your case 9) then you can view your number as a representation in base x+1. where each digit is a number between 0 and x.

This would give you significant performance gain as the algorithm would run in O(log n) time and require the same number of nodes as against O(n) in your case , n being the number of decimal digits of the larger of two addends.

Typically for the ease of your algorithm, you can choose a power of 10 as the base which fits in the range of your integer.

For example if your number be 1234567890987654321 and you want to store it in linked list choosing the base to be 10^8 then your representation should look like:

87654321-> 4567890 -> 123(little endian)