Add Two Numbers

Problem Statement

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 123 is represented as 3 -> 2 -> 1 -> 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

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.

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.

Solution

Recursion

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


def add(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 = add(
        l1.next if l1 else None,
        l2.next if l2 else None,
        carry
    )
    return ListNode(val, next_node)


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

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