Add Two Numbers

Add Two Numbers

What is this problem about?

The Add Two Numbers coding problem involves two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. You need to add the two numbers and return the sum as a linked list.

Why is this asked in interviews?

This is one of the most famous Linked List interview questions for companies like Amazon, Google, and Microsoft. It tests your ability to navigate linked structures, handle pointers, and implement carry logic simultaneously. It also evaluates how you handle edge cases like lists of different lengths.

Algorithmic pattern used

This utilizes the Linked List and Simulation interview pattern. You traverse both lists together, summing the values. If the sum exceeds 9, you pass the carry to the next node. You create new nodes as you move forward to store the resulting digits.

Example explanation

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Representing $342 + 465$

1. Add $2 + 5 = 7$.
2. Add $4 + 6 = 10$. Write $0$, carry $1$.
3. Add $3 + 4 + 1 = 8$. Result: 7 -> 0 -> 8 (Representing $807$).

Common mistakes candidates make

• Losing the Head: Forgetting to keep a reference to the starting node (the head) of the result list, making it impossible to return the full list.
• Carry at the End: If the last addition results in a carry (e.g., $5 + 5 = 10$), many forget to create one final node for the carry bit.
• Null Pointer Exceptions: Not checking if one list is longer than the other, leading to crashes when trying to access .next on a null node.

Interview preparation tip

Use a "dummy head" node to simplify the creation of the result list. It removes the need for a special if condition to handle the first node and makes your code much cleaner.