:orphan:

Add Two Numbers
===============

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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:**

|image1|

::


   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]

 

**Constraints:**

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

.. |image1| image:: https://assets.leetcode.com/uploads/2020/10/02/addtwonumber1.jpg

.. highlight:: python

Pattern
-------
Linked List, Math, Recursion

Solution
--------
When adding 2 numbers ``l1`` and ``l2``, the addition stops only when we run
out of nodes in ``l1`` and ``l2`` and the carry is empty. We get the next digit
using modulus and the carry using division. ::

    s = l1.val + l2.val + carry
    digit = s % 10
    carry = s // 10

If ``head`` is not set, set ``head = ListNode(digit)`` and ``node = head``.
Otherwise, set the next node ``node.next = ListNode(digit)`` and advance the
``node`` pointer.

Code
----

.. literalinclude:: ../problems/medium/add-two-numbers/add_two_numbers__approach_1.py
    :language: python
    :lines: 17-

Test
----
>>> from add_two_numbers__approach_1 import addTwoNumbers, ListNode
>>> l1 = ListNode.from_list([2, 4, 3])
>>> l2 = ListNode.from_list([5, 6, 4])
>>> addTwoNumbers(l1, l2).to_list()
[7, 0, 8]
>>> l1 = ListNode.from_list([0])
>>> l2 = ListNode.from_list([0])
>>> addTwoNumbers(l1, l2).to_list()
[0]
>>> l1 = ListNode.from_list([9, 9, 9, 9, 9, 9, 9])
>>> l2 = ListNode.from_list([9, 9, 9, 9])
>>> addTwoNumbers(l1, l2).to_list()
[8, 9, 9, 9, 0, 0, 0, 1]

Complexity
----------
| :math:`n` is the total number of nodes in both lists
| Time: :math:`O(n)` — single pass through both lists
| Auxiliary Space: :math:`O(1)`

.. autoclass:: add_two_numbers__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: add_two_numbers__approach_1.addTwoNumbers