Leetcode - 2. Add Two Numbers

Medium

Dec 24, 2025

#linked-list

#math

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes 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:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

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.

Constraints:

Notes

Intuition

Since the digits are stored in reverse order, we can add them just like we would on paper—starting from the ones place and carrying over when the sum exceeds 9.

Implementation

Create a dummy node for the result and maintain pointers for both input lists and the result. Track a carry value initialized to 0. While both lists have nodes, compute p1.val + p2.val + carry. The new digit is total % 10 and the new carry is total // 10. Create a new node and advance all pointers. After the main loop, process any remaining nodes in either list with the same carry logic.

Edge-cases

After processing both lists, the carry might still be non-zero (e.g., 99 + 1 = 100). Create a final node with the carry value if needed.

Time: O(n) — traverse both lists once
Space: O(1) — result list doesn't count toward space complexity

Complexity

Solution

from typing import Optional
from lcutils import ListNode

# 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()
        p1, p2, curr = l1, l2, dummy
        carry = 0

        while p1 and p2:
            tot = p1.val + p2.val + carry
            val = tot
            carry = 0

            if tot >= 10:
                val = tot % 10
                carry = tot // 10
            
            curr.next = ListNode(val)
            curr = curr.next
            p1 = p1.next
            p2 = p2.next

        while p1:
            tot = p1.val + carry
            val = tot
            carry = 0

            if tot >= 10:
                val = tot % 10
                carry = tot // 10
            
            curr.next = ListNode(val)
            curr = curr.next
            p1 = p1.next

        while p2:
            tot = p2.val + carry
            val = tot
            carry = 0
            if tot >= 10:
                val = tot % 10
                carry = tot // 10

            curr.next = ListNode(val)
            curr = curr.next
            p2 = p2.next

        if carry:
            curr.next = ListNode(carry)

        return dummy.next
        



if __name__ == "__main__":
    # Include one-off tests here or debugging logic that can be run by running this file
    # e.g. print(solution.two_sum([1, 2, 3, 4], 3))
    solution = Solution()