Reference: LeetCode
Difficulty: Medium

My Post: Java Solution Using Two Stacks

## Problem

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.

Example:

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:

### Reverse + Simulation

Note:

• Remember to reverse the return node before finishing.
• Notice the base case of reverse. Come up with some examples.

Time: $O(M + N)$ 2 ms
Space: $O(M + N)$

### Use Two Stacks

Use two stacks to simulate the add operation

Time: $O(M + N)$ 6 ms
Space: $O(M + N)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.