Add Two Numbers — Editorial

Opening the reading…

Intuitionwhy reverse-order digits make the addition direct

Each list stores the number backwards, so the first node is the units digit, the next node is the tens digit, and so on. That is exactly the order in which manual addition works: add the current digits, write the result digit, and carry the remaining value into the next column. No list reversal is needed.

At every position, add three values: the digit from the first list if one exists, the digit from the second list if one exists, and the carry from the previous position. The new node stores sum modulo 10, while sum divided by 10 becomes the carry for the next position. If one list ends first, treat its missing digits as zero.

The linked-list order matches the order required for carrying.

Approach

Create a dummy head and keep a pointer cur at it, because attaching every new node after a real previous node avoids a separate special case for the first result digit.

Continue while l1, l2, or carry still exists, because stopping when both input pointers are null would lose a final carry such as the one produced by 9 plus 1.

Start sum with carry, then add l1->val and advance l1 only when l1 is non-null, because a shorter list contributes zero after it ends and must not be dereferenced.

Do the same for l2, because the two lists can have different lengths and either one may run out first.

Set carry to sum divided by 10 and create a node containing sum modulo 10, because integer division keeps the next carry while modulo 10 keeps exactly one decimal digit in the current position.

Append the new node after cur and move cur forward, because leaving cur behind would overwrite the same next pointer on the following iteration.

Return dummy->next, because the dummy node is only a stable anchor and is not part of the sum.

Complexitylinear in the longer input list

MEASURE	BOUND	WHY
Time	O(max(n1, n2))	Each existing input node is read exactly once, and the loop performs at most one additional iteration for a final carry. The shorter list contributes no extra traversal after it ends, so the longer list determines the bound.
Space	O(1) extra space	The algorithm stores only pointers, the carry, and the current sum while building the required output list. The returned result nodes are output storage and are excluded from the extra-space bound; the output can contain max(n1, n2) or max(n1, n2) + 1 nodes.

Here n1 is the number of nodes in the first list and n2 is the number of nodes in the second list.

Annotated solutionC++ · iterative · one pass with a dummy head

CPPAdds corresponding digits in one pass and appends each resulting digit immediately.

#include <cstddef>

using namespace std;

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* cur = 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;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
        }

        return dummy->next;
    }
};

The loop condition carries the main correctness detail: it includes carry as well as the two input pointers. For example, after adding 9 and 1, both lists may be exhausted while carry is still 1, so the loop must run once more to create the leading result digit. The two null checks let the same body handle equal-length lists, unequal-length lists, and the final carry without duplicated cases.