Hommies

Posted on May 31

LeetCode Solution: 2. Add Two Numbers

#leetcode #dsa #programming #tutorial

Add Two Numbers 🟡 Medium: Summing Up Linked Lists Like a Pro!

Hey there, aspiring algorithm wizards! 👋 ahB1IK4YXF here, ready to demystify another classic LeetCode challenge. Today, we're tackling "Add Two Numbers," a fantastic problem that combines linked lists with some good old-fashioned arithmetic. Don't let the "Medium" tag scare you; we'll break it down step by step, and you'll see it's quite approachable once you grasp the core idea.

The Problem: Adding Numbers Represented by Linked Lists

Imagine you're back in elementary school, learning to add two multi-digit numbers. You line them up, add digit by digit from right to left, and carry over any extra tens. This problem is exactly that, but with a twist: our numbers are represented by linked lists, and their digits are stored in reverse order!

You're given two non-empty linked lists, l1 and l2. Each node contains a single digit (0-9). The digits are stored in reverse order, meaning the head of the list represents the "ones" place, the next node the "tens" place, and so on.

Your task? Add these two numbers and return the sum as a new linked list, also in reverse order.

Example 1: The Magic Reveal

l1 = [2,4,3] represents the number 342.
l2 = [5,6,4] represents the number 465.

If we add 342 + 465, we get 807.
The problem expects the output as [7,0,8], which is 807 in reverse order. Perfect!

Example 2: Simple Zeroes

l1 = [0], l2 = [0]
Output: [0]
(0 + 0 = 0)

Example 3: Handling Carries and Different Lengths

l1 = [9,9,9,9,9,9,9] (represents 9,999,999)
l2 = [9,9,9,9] (represents 9,999)
Output: [8,9,9,9,0,0,0,1] (represents 10,009,998)

Notice how the output list is longer than l2 and even l1 in some cases. This is crucial!

Intuition: Back to Basics (but with pointers!)

At its heart, this problem is just basic addition. Think about how you'd add 15 + 7:

Add the ones digits: 5 + 7 = 12.
Write down '2'.
Carry over '1' to the tens place.
Add the tens digits (including the carry): 1 (from 15) + 0 (from 7) + 1 (carry) = 2.
Write down '2'. Result: 22.

The fact that the linked list digits are in reverse order actually simplifies things for us! The head of the list (l1->val, l2->val) is already our "ones" place. So, we can just iterate through the lists from head to tail, performing digit-by-digit addition just like we would on paper, moving from right to left (which is left to right in our linked lists).

We need a variable to keep track of the carry as we move from one pair of digits to the next.

The Approach: A Step-by-Step Construction

We'll build our result linked list node by node. Here's the plan:

Initialize a Dummy Head: Creating a "dummy" node for our result list is a common and super handy trick in linked list problems. Instead of worrying about creating the very first node of the result list and handling it specially, we create a dummy node, attach our results to dummy.next, and then return dummy.next at the end. This keeps our code clean and consistent.
- ListNode* dummy = new ListNode();
- ListNode* current = dummy; (We'll use current to traverse and add new nodes to the result list).
Initialize Carry: We'll need a variable, carry, initialized to 0, to store any carry-over from previous additions.
- int carry = 0;
Iterate Through the Lists: We'll use a while loop that continues as long as there are digits in l1, or digits in l2, or a carry still needs to be processed. This handles lists of different lengths and the final carry if the sum results in an extra digit (e.g., 99 + 1 = 100).
- while (l1 || l2 || carry)
Calculate the Sum for Current Digits:
- Start total with the carry from the previous step.
- If l1 is not null, add its current digit (l1->val) to total and advance l1 to its next node.
- If l2 is not null, add its current digit (l2->val) to total and advance l2 to its next node.
- This gracefully handles cases where one list is shorter than the other – the if (l1) and if (l2) checks ensure we only add existing digits.
Determine the New Digit and Carry:
- The digit for our new result node is total % 10 (the remainder when divided by 10).
- The new carry is total / 10 (the quotient when divided by 10).
Create and Append New Node:
- Create a new ListNode with the calculated digit.
- Attach this new node to current->next.
- Move current forward to this newly added node: current = current->next; This prepares current to append the next digit.
Return the Result: After the loop finishes, all digits (and any final carry) will have been processed. Our dummy node's next pointer will point to the head of our actual result linked list.
- return dummy->next;
- Important C++ detail: The solution code also includes delete res; where res was the original dummy pointer. This is good practice to free the memory allocated for the initial dummy node itself, as we're returning res->next (the actual result list head) and no longer need the dummy.

The Code

Let's put it all together in C++:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // Create a dummy node to simplify list construction
        ListNode* dummy = new ListNode();
        ListNode* current = dummy; // 'current' will traverse and build the new list

        int carry = 0; // Initialize carry-over to 0

        // Loop as long as there are digits in either list or a carry remains
        while (l1 || l2 || carry) {
            int total = carry; // Start sum with any carry from previous addition

            // Add digit from l1 if it exists
            if (l1) {
                total += l1->val;
                l1 = l1->next; // Move to the next digit in l1
            }

            // Add digit from l2 if it exists
            if (l2) {
                total += l2->val;
                l2 = l2->next; // Move to the next digit in l2
            }

            // Calculate the digit for the new node and the new carry
            int digit = total % 10; // The current digit is the remainder
            carry = total / 10;   // The new carry is the quotient

            // Create a new node with the calculated digit
            current->next = new ListNode(digit);
            current = current->next; // Move 'current' to the newly added node
        }

        // The actual result list starts from dummy->next
        // We delete the initial dummy node to prevent memory leak (good practice in C++)
        ListNode* result = dummy->next;
        delete dummy; // 'res' in the original code snippet was 'dummy' here
        return result;      
    }
};

Note: The provided solution code snippet uses res as the initial dummy and dummy as the current pointer. My version uses dummy as the initial dummy and current as the traversing pointer, which is a common naming convention. The logic is identical.

Time & Space Complexity Analysis

Time Complexity: O(max(N, M))
- N is the number of nodes in l1, and M is the number of nodes in l2.
- We iterate through both linked lists exactly once. The loop runs for a number of times equal to the length of the longer list (plus possibly one more iteration if there's a final carry).
- Each operation inside the loop (addition, modulo, division, node creation) takes constant time.
- Therefore, the time complexity is directly proportional to 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, the sum list can be one node longer than the maximum length of l1 or l2 (e.g., adding 99 and 1 results in 100, which is three digits while the inputs were two and one).
- So, the number of new nodes created is proportional to the length of the longer input list.

Key Takeaways

Dummy Nodes: A powerful pattern for building new linked lists or modifying existing ones, eliminating edge cases for the head of the list.
Iterative Traversal: For problems requiring processing linked lists linearly, an iterative approach with pointers is often the most straightforward and efficient.
Handling Carries: This problem perfectly illustrates how to manage carry-over values in digit-by-digit operations, a fundamental concept in arithmetic and computer science.
Flexible Loop Conditions: The while (l1 || l2 || carry) condition is elegant. It ensures all digits from both lists are processed, and crucially, accounts for any final carry that might extend the result list.
Modular Arithmetic: Using % 10 to get the current digit and / 10 to get the carry is a classic trick for working with digits.

This problem is a fantastic introduction to linked lists and showcases how data structures can represent everyday concepts in interesting ways. Keep practicing, and you'll be a linked list master in no time!

Submission Details

Author: ahB1IK4YXF
Publishing Time: 2026-05-31 22:46:31
Problem Link: https://leetcode.com/problems/add-two-numbers/

DEV Community