https://leetcode.com/problems/add-two-numbers/
## タグ
## 概要
Linked Listとして数字が2つ与えられるので、合計した値をLinked Listとして返す。421という数字があった場合1->2->4と位が低い順にLinked Listになる。
## 方針
### Intuition
リストの先頭が1の位になっているので繰り上がりを考慮しつつ単純に足していけば良い。最後に繰り上がりだけ残っている場合に注意。
### 1の位から足していく
Time Complexity: $O(\max(n, m))$
Space Complexity: $O(1)$
※ 2つのリストの長さをそれぞれnとmとする
```python
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
def get_value(node):
if node is None:
return 0
return node.val
sentinel = ListNode()
prev = sentinel
carry = 0
while l1 or l2 or carry:
total = get_value(l1) + get_value(l2) + carry
prev.next = ListNode(total % 10)
prev = prev.next
carry = total // 10
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return sentinel.next
```