DEV Community

Hommies
Hommies

Posted on

LeetCode Solution: 2. Add Two Numbers

#leetcode #dsa #programming #tutorial

Unleash Your Inner Mathematician: Adding Numbers with Linked Lists (LeetCode #2)

Hey awesome developers! 👋 Ever wondered how computers perform basic arithmetic with a twist? Today, we're diving into a classic LeetCode problem that might seem simple on the surface but introduces some fundamental data structures and algorithmic thinking: "Add Two Numbers".

This problem is a fantastic way to sharpen your skills with linked lists and understand how to simulate everyday operations like addition programmatically. Don't worry if linked lists sound intimidating; we'll break it down piece by piece!

📚 Problem Explanation: Digits in Reverse!

Imagine you have two numbers, but instead of seeing them as regular integers like 342 or 465, their digits are stored in a special way: a linked list, and in reverse order!

Each "node" in our linked list holds a single digit. For example:

  • The number 342 would be represented as a linked list: 2 -> 4 -> 3
  • The number 465 would be: 5 -> 6 -> 4

Our mission? To add these two numbers together, digit by digit, and return their sum as another linked list, also in reverse order.

Let's look at Example 1:

  • Input: l1 = [2,4,3] (represents 342)
  • Input: l2 = [5,6,4] (represents 465)
  • Output: [7,0,8] (represents 807)

See? 342 + 465 = 807. The [7,0,8] linked list correctly gives us 807 in reverse!

A few important rules:

  • The lists are non-empty.
  • Digits are non-negative (0-9).
  • No leading zeros (unless the number itself is 0, like [0]).

🤔 Intuition: How Do We Add Numbers By Hand?

Before we jump into code, let's think about how you add numbers manually:

  342
+ 465
-----
Enter fullscreen mode Exit fullscreen mode
  1. Start from the rightmost digits: 2 + 5 = 7. Write down 7.
  2. Move to the next digits (tens place): 4 + 6 = 10. Write down 0, and carry over 1 to the hundreds place.
  3. Move to the next digits (hundreds place): 3 + 4 + (the carried-over 1) = 8. Write down 8.

The result is 807.

This "digit-by-digit, with a carry-over" strategy is exactly what we'll replicate with our linked lists! Since the digits are already in reverse order, it's like we're already starting from the rightmost digit (the units place)! This is a huge hint.

🪜 Approach: Step-by-Step with Linked Lists

Our approach will mimic manual addition:

  1. Initialize:

    • Create a dummy node. This is a common trick in linked list problems. It acts as a placeholder for the head of our new list. We'll eventually return dummy.next.
    • Create a current pointer, initialized to dummy. This pointer will help us build our result list by moving forward.
    • Initialize a carry variable to 0. This will store any carry-over from the previous sum.

  2. Iterate through the lists: We need to keep adding digits as long as there are digits in either l1 or l2, or if there's still a carry left over from a previous addition. This while loop condition is crucial: while l1 or l2 or carry:

  3. Calculate the sum for the current position:

    • Start total_sum with the carry from the previous step.
    • If l1 is not None (meaning there's a digit in the first number), add l1.val to total_sum and move l1 to its next node (l1 = l1.next).
    • If l2 is not None (meaning there's a digit in the second number), add l2.val to total_sum and move l2 to its next node (l2 = l2.next).

  4. Determine the current digit and new carry:

    • The digit for our result list at the current position will be total_sum % 10 (the remainder after dividing by 10).
    • The new carry will be total_sum // 10 (the integer division by 10).

  5. Build the result list:

    • Create a new ListNode with the calculated digit.
    • Append this new node to our result list: current.next = new_node.
    • Move current forward to this new node: current = current.next.

  6. Return: Once the loop finishes, we've built our entire sum list. Return dummy.next to get the actual head of the sum list (skipping the initial placeholder dummy node).

This process continues until both input lists are exhausted AND there's no carry left.

💻 Code: Bringing It to Life (Python) 

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node to simplify handling the head of the result list
        dummy_head = ListNode()
        # 'current' pointer will build our new linked list
        current = dummy_head

        # Initialize carry to 0
        carry = 0

        # Loop as long as there are digits in either list or a carry exists
        while l1 or l2 or carry:
            # Get the value from l1 (or 0 if l1 is exhausted)
            val1 = l1.val if l1 else 0
            # Get the value from l2 (or 0 if l2 is exhausted)
            val2 = l2.val if l2 else 0

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

            # Determine the digit for the new node (units place of total_sum)
            digit = total_sum % 10
            # Determine the new carry (tens place of total_sum)
            carry = total_sum // 10

            # Create a new node with the calculated digit
            current.next = ListNode(digit)
            # Move our 'current' pointer forward to the new node
            current = current.next

            # Move l1 and l2 pointers forward if they are not exhausted
            if l1:
                l1 = l1.next
            if l2:
                l2 = l2.next

        # The first node (dummy_head) was just a placeholder.
        # The actual result list starts from dummy_head.next.
        return dummy_head.next
Enter fullscreen mode Exit fullscreen mode

⏱️ Time & Space Complexity Analysis

Time Complexity: O(max(m, n))

  • m is the number of nodes in l1.
  • n is the number of nodes in l2.
  • We iterate through both linked lists exactly once. The loop runs for a number of times proportional to the length of the longer list. This makes the time complexity linear with respect to the length of the longer input list.

Space Complexity: O(max(m, n))

  • In the worst-case scenario, the resulting linked list can have max(m, n) + 1 nodes (if there's a final carry-over). We are creating a new linked list to store the sum. Therefore, the space complexity is also linear with respect to the length of the longer input list.

🌟 Key Takeaways

  1. Linked Lists for Arithmetic: This problem beautifully demonstrates how linked lists can be used to represent and manipulate numbers, especially useful when dealing with very large numbers that might exceed standard integer types.
  2. The "Dummy Node" Trick: Using a dummy_head node is a super common and effective pattern in linked list problems. It simplifies code by always having a node to attach to, eliminating special checks for an empty result list or when adding the very first node.
  3. Carry Handling: Understanding how to manage the carry digit is fundamental to correctly implementing addition, whether manually or programmatically.
  4. Simulating Manual Processes: Many algorithmic problems can be solved by breaking them down into steps that mimic how we would solve them in real life.

This problem is a fantastic stepping stone for more complex linked list manipulations and numerical algorithms. Keep practicing, and you'll be a LeetCode master in no time! Happy coding!

Submission Details:
Author Account: p1Hzd8mRM8
Time Published: 2026-05-16 22:27:48

Top comments (0)