LeetCode 2 — Add Two Numbers

Pattern: Linked List Digit Addition with Carry

This problem follows the digit-by-digit addition pattern, where a number is represented as a sequence of digits and we process one digit at a time. Since the digits are stored in reverse order, the head of the linked list represents the ones place, the next node represents the tens place, and so on. This makes the problem easier because we can add from the head directly, just like starting addition from the rightmost digit in normal arithmetic.

The main idea is to maintain a carry while traversing both linked lists. At each step, take the current digit from both lists. If one list is shorter and has already ended, treat its digit as 0. Add both digits along with the carry. The current result node stores total % 10, because each node can only hold one digit. The new carry becomes total // 10.

A very common linked list technique used here is the dummy head pattern. When building a new linked list, a dummy node helps avoid special handling for the first node. We keep a tail pointer that always points to the last node in the result list. Every time we compute a digit, we create a new node and attach it to tail.next, then move tail forward.

The loop must continue while either linked list still has nodes or there is a remaining carry. This final carry is important for cases like 9 + 1 = 10, where an extra node must be added at the end. This pattern is useful whenever a problem asks you to simulate arithmetic using linked lists, arrays, or strings.

Similar LeetCode Problems

• 2. Add Two Numbers

• 445. Add Two Numbers II

• 66. Plus One

• 67. Add Binary

• 415. Add Strings

• 989. Add to Array-Form of Integer

• 369. Plus One Linked List

• 43. Multiply Strings

Solution

# 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]:

        dummyHead = ListNode(0)
        tail = dummyHead
        carry = 0

        while l1 is not None or l2 is not None or carry != 0:
            digit1 = l1.val if l1 is not None else 0
            digit2 = l2.val if l2 is not None else 0

            total = digit1 + digit2 + carry
            digit = total % 10
            carry = total // 10

            tail.next = ListNode(digit)
            tail = tail.next

            l1 = l1.next if l1 is not None else None
            l2 = l2.next if l2 is not None else None

        return dummyHead.next