Add Two Numbers

Problem Description

You are given 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. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Examples

Constraints

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Digit-by-Digit Addition with Carry

Since the digits are stored in reverse order (least significant digit first), the linked list aligns perfectly with how we perform manual addition. We iterate through both linked lists simultaneously. At each step:

• Compute the sum of the digits from both nodes (if present) plus the carry from the previous step.
• Update the carry for the next step: carry = sum / 10.
• Create a new node with the value sum % 10 and append it to our result list.
• Move our list pointers forward. If the loop ends but a carry remains, we append one final node with value carry.

Solution 1: Direct Carry Addition

Iterate through nodes, accumulating digit sums and carrying remainders forward.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }
        return dummy.next;
    }
}

# 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]:
        dummy = ListNode(0)
        curr = dummy
        carry = 0
        
        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next
                
            carry = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next
            
        return dummy.next

/**
 * 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) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;
        int carry = 0;

        while (l1 || l2 || carry) {
            int sum = carry;
            if (l1) {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2) {
                sum += l2->val;
                l2 = l2->next;
            }
            carry = sum / 10;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
        }
        return dummy->next;
    }
};

Complexity Analysis

• Time Complexity: O(max(m, n)) where m and n are the lengths of the two linked lists. We process each node once.
• Space Complexity: O(1) auxiliary space (excluding the result list).

Where It Breaks

This solution allocates a new list. If we are required to merge the values in-place into one of the input lists to conserve memory, we must modify the pointer redirections accordingly.

Common Mistakes

• Incorrect check conditions in loop: Terminating the loop when one list becomes null but a carry remains. If the carry is 1, it must be appended as a final node.
• Null Pointer Dereference: Accessing l1.val when l1 is null. You must guard list reads with null checks.

Frequently Asked Questions

Why use a dummy node? A dummy node provides a fixed root pointer to the result list, removing the need to write separate checks for initializing the list head.

How does this handle lists of unequal lengths? If one list is shorter, we treat its missing values as 0 and continue adding carry and values from the longer list.

← All Problems