Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Add Two Numbers
• Main tags: Linked List, Math, Recursion

What the problem is really asking

Two linked lists represent two non-negative integers. Each node stores one digit, and the digits are already in reverse order, so the ones place comes first.

That means 2 -> 4 -> 3 stands for 342, and 5 -> 6 -> 4 stands for 465.

The job is to return a brand-new linked list for the sum. In the example above, 342 + 465 = 807, so the answer is 7 -> 0 -> 8.

The key insight

This problem looks harder than it is because it uses linked lists instead of arrays or integers.

The trick is to notice that the reversed order is helping, not hurting. Normal addition starts from the rightmost digit. Here, the rightmost digit is already the head of each list, so the algorithm can process both lists from left to right exactly once.

That turns the whole problem into regular grade-school addition:

• add the current two digits
• include any carry from the previous step
• write down the ones digit
• carry the tens digit into the next step

How to derive the optimal solution

The cleanest way to think about it is to simulate what a person would do on paper.

1. Keep one pointer on each list and a carry value.
2. Read the current digit from each list. If one list is shorter, treat its missing digit as 0.
3. Compute total = left_digit + right_digit + carry.
4. Put total % 10 into the answer list.
5. Set carry = total // 10.
6. Move both pointers forward and repeat until both lists are exhausted and there is no carry left.

The answer list is built one node at a time. A dummy head node makes the append logic simple because the first real digit is handled exactly the same way as every later digit.

Best approaches

The iterative version is the best default:

• Time: O(max(m, n))
• Extra space: O(1) beyond the output list
• Why it is best: one pass, no reversing, no integer conversion, no recursion depth risk

A recursive version also works and has the same time complexity, but in Python it adds call-stack overhead without making the logic clearer. For production-style code, the iterative solution is the better choice.

Python solution

from typing import Optional


# LeetCode provides the ListNode class.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


class Solution:
    def addTwoNumbers(
        self,
        first_number: Optional[ListNode],
        second_number: Optional[ListNode],
    ) -> Optional[ListNode]:
        dummy_head = ListNode(0)
        tail = dummy_head
        carry = 0

        left = first_number
        right = second_number

        # Keep going while there is still input to process or a carry to flush.
        while left is not None or right is not None or carry:
            carry, digit = self._compute_next_digit(left, right, carry)

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

            left = left.next if left is not None else None
            right = right.next if right is not None else None

        return dummy_head.next

    @staticmethod
    def _compute_next_digit(
        left: Optional[ListNode],
        right: Optional[ListNode],
        carry: int,
    ) -> tuple[int, int]:
        left_digit = left.val if left is not None else 0
        right_digit = right.val if right is not None else 0
        total = left_digit + right_digit + carry
        next_carry, digit = divmod(total, 10)
        return next_carry, digit

Why this works

Each loop iteration finalizes exactly one digit of the answer. Because the input lists are reversed, the algorithm always has the correct next pair of digits ready at the front of the lists.

The carry variable is the only cross-step state that matters. Once that is tracked correctly, the rest of the solution is just careful linked-list construction.

The easiest way to remember this problem is:

reverse-order digits mean no preprocessing is needed. Just walk both lists, add like elementary-school math, and build the result as you go.