2. Add Two Numbers - Explanation

Problem Link

Description

You are given two non-empty linked lists, l1 and l2, where each represents a non-negative integer.

The digits are stored in reverse order, e.g. the number 321 is represented as 1 -> 2 -> 3 -> in the linked list.

Each of the nodes contains a single digit. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Return the sum of the two numbers as a linked list.

Example 1:

Input: l1 = [1,2,3], l2 = [4,5,6]

Output: [5,7,9]

Explanation: 321 + 654 = 975.

Example 2:

Input: l1 = [9], l2 = [9]

Output: [8,1]

Constraints:

  • 1 <= l1.length, l2.length <= 100.
  • 0 <= Node.val <= 9


Recommended Time & Space Complexity

You should aim for a solution with O(m + n) time and O(1) space, where m is the length of list l1 and n is the length of list l2.


Hint 1

Try to visualize the addition of two numbers. We know that the addition of two numbers is done by starting at the one's digit. We add the numbers by going through digit by digit. We track the extra value as a carry because the addition of two digits can result in a number with two digits. The carry is then added to the next digits, and so on. How do you implement this in case of linked lists?


Hint 2

We track the extra value, carry, here as well. We iterate through the lists l1 and l2 until both lists reach null. We add the values of both nodes as well as the carry. If either of the nodes is null, we add 0 in its place and continue the process while tracking the carry simultaneously. Once we complete the process, if we are left with any carry, we add an extra node with that carry value and return the head of the result list.


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

Intuition

We add the two linked lists exactly like adding two numbers on paper.

Each node contains one digit, and since the lists are stored in reverse order, the head contains the ones place — making addition easy.
At every step:

  1. Take a digit from l1 (or 0 if it’s finished)
  2. Take a digit from l2 (or 0 if it’s finished)
  3. Add them with the incoming carry
  4. Create a new node for the current digit (sum % 10)
  5. Pass the new carry (sum // 10) forward using recursion

The recursion naturally processes digits from left to right and stops only when:

  • both lists are fully processed and
  • no carry remains.

Algorithm

  1. Define a recursive function add(l1, l2, carry):

    • If l1, l2 are both None and carry is 0, return None.
    • Extract:
      • v1 = l1.val if l1 exists, else 0
      • v2 = l2.val if l2 exists, else 0
    • Compute:
      • total = v1 + v2 + carry
      • carry, digit = divmod(total, 10)
    • Recursively compute the next node using:
      • l1.next if exists
      • l2.next if exists
      • updated carry
    • Return a node with value digit whose next is the recursive result.

  2. In addTwoNumbers, call:

    • return add(l1, l2, 0)
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def add(self, l1: Optional[ListNode], l2: Optional[ListNode], carry: int) -> Optional[ListNode]:
        if not l1 and not l2 and carry == 0:
            return None

        v1 = l1.val if l1 else 0
        v2 = l2.val if l2 else 0

        carry, val = divmod(v1 + v2 + carry, 10)

        next_node = self.add(
            l1.next if l1 else None,
            l2.next if l2 else None,
            carry
        )
        return ListNode(val, next_node)

    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        return self.add(l1, l2, 0)

Time & Space Complexity

  • Time complexity: O(m+n)O(m + n)
  • Space complexity: O(m+n)O(m + n)

Where mm is the length of l1l1 and nn is the length of l2l2.

2. Iteration

Intuition

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.

Algorithm

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

Time & Space Complexity

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

Where mm is the length of l1l1 and nn is the length of l2l2.