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.
I’ve tried direct recursion without reversing, but couldn’t make it work.
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]  [0, 0, 1]
Reverse + Simulation
Remember to reverse the return node before finishing.
Notice the base case of reverse. Come up with some examples.