You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Note: You may assume the two numbers do not contain any leading zero, except the number $0$ itself.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Use Stack.

Analysis

I’ve tried direct recursion without reversing, but couldn’t make it work.

Test Case:

1 2 3 4 5 6 7 8 9 10 11 12

// When one list is longer than the other. [0, 1] [0, 1, 2] [0, 2, 2] // When one list is null, which means an empty list. [] [0, 1] [0, 1] // When sum could have an extra carry of one at the end, which is easy to forget. [9, 9] [1] [0, 0, 1]

Reverse + Simulation

Note:

Remember to reverse the return node before finishing.

Notice the base case of reverse. Come up with some examples.