Add Two Numbers

Medium · Linked List · Explanation and code example

Iteration

How it works

We simulate normal addition the same way we do on paper — digit by digit.

The linked lists store numbers in reverse order, so the first nodes represent the 1’s place.
This makes addition straightforward:

  • Add the two digits.
  • Add the carry from the previous step.
  • Save the resulting digit (sum % 10) into a new node.
  • Update the carry (sum // 10).
  • Move both pointers forward.

We continue until both lists are finished AND no carry remains.
A dummy node helps us easily build and return the final linked list.

Steps

  1. Create:

    • A dummy node (to build the answer)
    • A pointer cur pointing to dummy
    • An integer carry = 0

  2. Loop while l1 exists, l2 exists, or carry is non-zero:

    • Read the current digit of each list (0 if that list already ended)
    • Compute sum = v1 + v2 + carry
    • Update: carry = sum // 10 digit = sum % 10
    • Append a new node containing digit
    • Move the pointers l1, l2, and cur forward

  3. Return dummy.next (the head of the result list)

This ensures correct handling of:

  • different lengths of input lists
  • leftover carry
  • building the result in one pass

Complexity

  • Time complexity: O(max(m, n))
    • This is asymptotically equivalent to O(m + n).
  • Space complexity:
    • O(1) extra space.
    • O(max(m, n)) for the output list.

Where m is the length of l1 and n is the length of l2.

Things to watch for

Forgetting the Final Carry

When both lists are exhausted, there may still be a carry of 1 (e.g., 999 + 1 = 1000). Stopping the loop early without checking for remaining carry produces an incorrect result.

Not Handling Lists of Different Lengths

When one list is longer than the other, the loop must continue processing the remaining nodes. Using l1 and l2 instead of l1 or l2 stops too early.

Python code example

from typing import Optional

# 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()
        cur = dummy

        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0

            # new digit
            val = v1 + v2 + carry
            carry = val // 10
            val = val % 10
            cur.next = ListNode(val)

            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy.next

C++ code example

/**
 * 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();
        ListNode* cur = dummy;

        int carry = 0;
        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            int v1 = (l1 != nullptr) ? l1->val : 0;
            int v2 = (l2 != nullptr) ? l2->val : 0;

            int val = v1 + v2 + carry;
            carry = val / 10;
            val = val % 10;
            cur->next = new ListNode(val);

            cur = cur->next;
            l1 = (l1 != nullptr) ? l1->next : nullptr;
            l2 = (l2 != nullptr) ? l2->next : nullptr;
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations