LeetCode Solution: 2. Add Two Numbers

#leetcode #dsa #programming #tutorial

🚀 Cracking LeetCode #2: Adding Two Numbers Like a Pro (with Linked Lists!) 🚀

Hey there, future coding rockstars! 👋 Today, we're diving into a LeetCode classic that often stumps beginners but is incredibly satisfying once you "get" it. We're talking about LeetCode Problem #2: Add Two Numbers.

This problem is a fantastic introduction to manipulating linked lists and thinking about how computers handle fundamental operations like arithmetic. Ready to conquer it? Let's go!

The Problem Explained: Adding Numbers, But Backwards! 🤯

Imagine you want to add two big numbers, like 342 and 465. Normally, you'd write them down and add them from right to left (units, tens, hundreds, etc.), carrying over any extra digits.

Now, imagine these numbers aren't stored as regular integers but as linked lists. If you're new to linked lists, think of them as a chain of boxes (nodes), where each box holds a value and points to the next box in the chain.

The twist? The digits are stored in reverse order!

l1 = [2,4,3] actually represents the number 342. (3 -> 4 -> 2, but read from the head: 2 is units, 4 is tens, 3 is hundreds).
l2 = [5,6,4] actually represents the number 465.

Our goal is to add these two numbers (342 + 465) and return their sum (807) also as a linked list in reverse order: [7,0,8].

Let's look at the examples:

Example 1:
Input: l1 = [2,4,3] (342), l2 = [5,6,4] (465)
Output: [7,0,8] (807)
Explanation: 2 + 5 = 7. 4 + 6 = 10 (0 with carry 1). 3 + 4 + 1 (carry) = 8. So, [7, 0, 8].

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]
Explanation: 0 + 0 = 0.

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
Explanation: This one shows longer lists and the need to handle a final carry! 9,999,999 + 9,999 = 10,009,998.

The "Aha!" Moment: Mimicking Manual Addition 💡

The key to solving this problem lies in realizing that since the digits are already in reverse order, the head of each linked list contains the least significant digit (the "ones" place). This is exactly where we start when we add numbers by hand!

So, the "aha!" moment is: we can simply iterate through both linked lists simultaneously, adding digits just like we would with pen and paper.

For each "place value":

Add the corresponding digits from l1 and l2.
Don't forget to add any carry from the previous addition!
The sum of these three numbers (digit1 + digit2 + carry) will give us a total_sum.
The new digit for our result list will be total_sum % 10 (the remainder when divided by 10).
The new carry for the next iteration will be total_sum // 10 (the quotient when divided by 10).

We continue this process until we've gone through both lists and handled any final carry.

The Step-by-Step Approach 🚶‍♂️

Let's break down the logic into concrete steps:

Initialize a Dummy Head: Create a dummy node. This is a common trick with linked lists! It acts as a placeholder for the beginning of our result list. We'll eventually return dummy.next to skip this placeholder.
Current Pointer for Result: Create a res pointer and point it to dummy. This res pointer will move along as we build our new linked list.
Initialize Carry: Set a carry variable to 0. This will store any carry-over digit from our additions.
Loop Until Done: We need to keep adding as long as there are digits in l1, digits in l2, or a carry remaining. So, our loop condition will be while l1 or l2 or carry:.
Get Current Digits:
- If l1 exists, get its val. Otherwise, consider it 0.
- If l2 exists, get its val. Otherwise, consider it 0.
- This handles lists of unequal lengths gracefully.
Calculate Sum: total_sum = val1 + val2 + carry.
New Digit and New Carry:
- The digit for our new node is total_sum % 10.
- The carry for the next iteration is total_sum // 10.
Create and Append New Node:
- Create a new ListNode with the calculated digit.
- Append this new node to our result list: res.next = new_node.
- Move our res pointer forward: res = res.next.
Advance Input Pointers:
- If l1 is not None, move l1 = l1.next.
- If l2 is not None, move l2 = l2.next.
Return Result: Once the loop finishes, return dummy.next. This skips our initial placeholder node and gives us the actual head of our sum list.

This approach perfectly mimics how we'd add numbers by hand, ensuring we handle carries and lists of different lengths.

The Code 🧑‍💻

Here's the Python implementation based on our approach:

# Definition for singly-linked list.
# This part is usually provided by LeetCode or you define it yourself.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

from typing import Optional

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:

        # 1. Initialize a dummy head for the result list
        dummy_head = ListNode()
        # 2. 'current' pointer to build the result list
        current = dummy_head 

        # 3. Initialize carry to 0
        carry = 0

        # 4. Loop as long as there are digits in either list OR a carry remains
        while l1 is not None or l2 is not None or carry != 0:
            # 5. Get current digits (or 0 if list is exhausted)
            val1 = l1.val if l1 is not None else 0
            val2 = l2.val if l2 is not None else 0

            # 6. Calculate the total sum for the current position
            total_sum = val1 + val2 + carry

            # 7. Determine the digit for the current node and the new carry
            new_digit = total_sum % 10
            carry = total_sum // 10

            # 8. Create a new node and append it to our result list
            current.next = ListNode(new_digit)
            # Move the 'current' pointer forward
            current = current.next

            # 9. Advance input list pointers if they exist
            if l1 is not None:
                l1 = l1.next
            if l2 is not None:
                l2 = l2.next

        # 10. Return the actual head of the sum list (skipping the dummy_head)
        return dummy_head.next

Time & Space Complexity Analysis ⏱️📏

Understanding how much time and memory your solution uses is crucial for competitive programming!

Time Complexity: O(max(N, M))
- Where N is the number of nodes in l1 and M is the number of nodes in l2.
- We iterate through both linked lists at most once. The loop continues for a number of iterations equal to the length of the longer list, plus potentially one more if there's a final carry. Hence, the time taken scales linearly with the length of the longer input list.
Space Complexity: O(max(N, M))
- We create a new linked list to store the sum. In the worst case (e.g., adding two numbers like [9,9,9] and [1]), the result list can be one node longer than the longer input list ([0,0,0,1]).
- Therefore, the space used to store the result scales linearly with the length of the longer input list.

Key Takeaways ✨

Simulate Manual Processes: Many problems, especially arithmetic ones, can be solved by translating your "pen-and-paper" method into code.
The Power of a Dummy Node: A dummy head node is a fantastic pattern for simplifying linked list operations, especially when you're building a new list or might need to modify the original head. It avoids annoying edge cases where you'd have to handle the first node creation separately.
Handling Carries and Unequal Lengths: This problem is a great example of how to manage state (the carry) between iterations and gracefully handle inputs of different sizes.
Linked Lists for Big Numbers: Linked lists are often used in computer science to represent numbers of arbitrary length, exceeding what standard integer types can hold.

Congratulations! You've just walked through a fundamental LeetCode problem, learned about linked lists, and developed a solid approach. Keep practicing, and you'll be crushing those interviews in no time!

Authored by p1Hzd8mRM8. Published on 2026-05-16 22:58:14.