Add Two Numbers II

Add Two Numbers II

What is this problem about?

The Add Two Numbers II interview question is a twist on the previous problem. This time, the digits are stored in forward order (the most significant digit is at the head). You are not allowed to reverse the input lists.

Why is this asked in interviews?

Companies like Goldman Sachs and TikTok ask this to see if you can solve a problem when the natural traversal (left to right) is the opposite of the mathematical requirement (right to left). It tests your knowledge of auxiliary data structures like stacks or recursion.

Algorithmic pattern used

Since we need to process the digits from last to first, but linked lists only move forward, the Stack interview pattern is ideal. By pushing all nodes onto two stacks, we can pop them to access the digits in reverse order. Alternatively, you can use Recursion to reach the end of the lists before beginning the addition as the stack unwinds.

Example explanation

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)

1. Push all digits of List 1 to Stack A: [7, 2, 4, 3]
2. Push all digits of List 2 to Stack B: [5, 6, 4]
3. Pop $3$ and $4$: Sum $7$, carry $0$.
4. Pop $4$ and $6$: Sum $10$. Digit $0$, carry $1$.
5. ...And so on, building the new list nodes from right to left.

Common mistakes candidates make

• Trying to align by length: Attempting to manually pad the shorter list with zeros can be very error-prone.
• Memory Overhead: Using a stack is $O(N)$ space. If the interviewer asks for $O(1)$ extra space, you must reverse the lists (if allowed) or use a much more complex recursive depth-matching approach.

Interview preparation tip

Whenever you need to process a Linked List in reverse order but can't change the list itself, your first thought should always be a Stack. It’s the most straightforward way to reverse processing order.