LeetCode Solutions
#2 — Add Two Numbers

Problem statement

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.

Example 1:

Example 2:

Example 3:

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.

The naive way

The most straightforward idea: traverse each list, reconstruct the integer (by multiplying by powers of 10 as we go), add them, and then build a new reversed linked list from the sum. In Python it’s tempting because integers have arbitrary precision.

def get_number(head):
    num = 0
    place = 1
    while head:
        num += head.val * place
        place *= 10
        head = head.next
    return num

# Then add and rebuild ... but don't do this.
            

Initial complexity

This works for small inputs, but the problem allows up to 100 digits — numbers far beyond what a 64‑bit integer can hold. In languages like C++ or Java you’ll overflow immediately. Even in Python, it misses the point: the problem is designed to teach carry simulation on linked lists, not big‑integer libraries.

Simulating grade‑school addition

Since the digits are stored in reverse (least significant first), we can add digit by digit exactly as we did in elementary school. Walk both lists together, sum the current digits plus any carry from the previous step, store sum % 10 in a new node, and pass sum // 10 to the next position. When one list is exhausted, treat missing digits as 0. At the end, if a carry remains, append one more node.

The dummy head trick keeps the code clean: we never need to check whether the result list is empty.

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        current = dummy
        carry = 0

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            total = val1 + val2 + carry
            carry = total // 10
            current.next = ListNode(total % 10)
            current = current.next

            if l1: l1 = l1.next
            if l2: l2 = l2.next

        return dummy.next
            

Let’s trace example l1 = [2,4,3] , l2 = [5,6,4]:

Final complexity

Time complexity: O(max(m, n)) — we traverse each node exactly once.
Space complexity: O(max(m, n)) for the new list (if we ignore the output, auxiliary space is O(1)).

References & further reading

• LeetCode Add Two Numbers Problem Page — official problem and discussion forums.
• Wikipedia: Carry (arithmetic) — the mechanism that makes it work.
• GNU MP (GMP) — a real‑world arbitrary‑precision arithmetic library.
• GeeksforGeeks: Add two numbers represented by linked lists — alternative explanations and implementations.

Can't get enough from lumænaut? Read this...

• Chapter 2 | Everything I Don't Know About Blogging — the logbook behind the site: domains, SEO, plugins, and learning in public.
• The 8 Algorithm Paradigms — eight mental models you’ll keep reusing across problems, interviews, and production code.
• How the Game Loop Works — the heartbeat of a game frame: update, render, and steady timing in plain language.