LeetCode Study Note | Problem 2: Add Two Numbers

🧠 Problem Summary

Given two non-empty linked lists representing two non-negative integers in reverse order (each node contains a single digit), return the sum as a new linked list, also in reverse order.

Example:

Input:  (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

✅ Recommended Approach: Simulated Digit-by-Digit Addition

This approach mimics manual addition, performing it one digit at a time from least to most significant, and carefully handling carry-over.

Steps:

1. Initialize:

   • A dummy head node to simplify list operations.

   • A current pointer for constructing the result.

   • A carry variable set to 0.

2. Iterate through both lists:

   • Sum corresponding digits from both lists and the carry.

   • Create a new node with the digit sum % 10.

   • Update the carry as sum / 10.

3. After traversal:

   • If there’s a non-zero carry left, add one final node.

Why This Works:

• Handles arbitrarily large numbers (not limited by language types).

• Efficient: no string or integer conversions.

• Scalable and adaptable to follow-up problems (e.g., lists in forward order).

⚠️ A Common Incorrect Approach: Converting to Integers

Description:

One might think to convert the two linked lists into numbers, add them, and then convert the result back into a linked list:

StringBuilder sb = new StringBuilder();
// build the number from l1 and l2 by reversing digits
int num1 = Integer.valueOf(sb1.reverse().toString());
int num2 = Integer.valueOf(sb2.reverse().toString());
int sum = num1 + num2;

Why This Is Problematic:

1. Integer Overflow

   Java’s Integer and even Long types can’t represent very large numbers. Lists with more than 10–19 digits will fail.

2. Incorrect Character Conversion

   Using Integer.valueOf(char) returns the character’s Unicode code point, not the digit value.

   For example:

   Integer.valueOf('7') → 55 (wrong)

   '7' - '0' → 7 (correct)

3. Unnecessary Complexity

   This approach involves multiple conversions and reversals, which can be error-prone and less efficient than directly working with the list structure.

🌱 My Learning Reflection

Initially, I thought converting the list into numbers and using simple arithmetic would be straightforward. It worked for small test cases but failed to scale due to integer limitations and subtle bugs.

After studying the recommended solution, I understood how digit-by-digit simulation avoids overflow and is both safer and more extensible.

This process deepened my understanding of:

• Linked list manipulation

• How to simulate arithmetic operations

• Why respecting data structure constraints is crucial in algorithm design

💬 Final Thoughts

This problem is a great example of how computer science often mirrors real-world reasoning—manual methods like long addition can be more reliable than shortcuts. Understanding why a certain approach works is just as important as how to implement it.