[/dsa/leetcode]

2 - Add Two Numbers

Friday, 18 September 2026

<medium> [problem]

Reverse order means the digits arrive least significant first, which is exactly the order schoolbook addition wants, so one walk with a carry builds the answer.

{linked list}{math}

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node 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.

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Input: l1 = [0], l2 = [0]
Output: [0]

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

  • The number of nodes in each list is in the range [1, 100]
  • 0 <= Node.val <= 9
  • The lists represent numbers without leading zeros

Approach

It is column addition, walked once. At each step take a digit from each list plus whatever carried in, write sum % 10, keep sum / 10 and at the end put the values of carries at the end of the list.

l1: 9 -> 9 -> 9 -> 9
l2: 9 -> 9

    carry  9+9   9+9   9+0   9+0   done
      0     8     9     9     9      1
    carry   1     1     1     1      -
out:        8  -> 9  -> 9  -> 9  -> 1
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &dummy;
        int carry = 0;
        while(l1 && l2) {
            int sum = l1->val + l2->val + carry;
            int digit = sum % 10;
            carry = sum / 10;
            tail->next = new ListNode(digit);
            tail = tail->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1) {
            int sum = l1->val + carry;
            int digit = sum % 10;
            carry = sum / 10;
            tail->next = new ListNode(digit);
            tail = tail->next;
            l1 = l1->next;
        }
        while(l2) {
            int sum = l2->val + carry;
            int digit = sum % 10;
            carry = sum / 10;
            tail->next = new ListNode(digit);
            tail = tail->next;
            l2 = l2->next;
        }
        if(carry > 0) {
            tail->next = new ListNode(carry);
            tail = tail->next;
        }
        return dummy.next;
    }
};

At most one of the two middle loops ever runs, since the first loop only exits when a list is exhausted. The carry still has to be threaded through them, because a tail of 9s can keep propagating one long after the other number ended. All three loops are doing the same thing to different operands though, and the leftover carry is just one more column where both digits are zero. Treat a missing node as a zero and put carry in the loop condition, and the whole thing collapses:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* tail = &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;
            tail->next = new ListNode(sum % 10);
            tail = tail->next;
        }
        return dummy.next;
    }
};
  • time: O(max(m, n)) - one pass, one node per output digit
  • space: O(1) auxiliary - the output list is the answer, not scratch space
quantinium © 2026