# 445. Add Two Numbers II

{% embed url="<https://leetcode.com/problems/add-two-numbers-ii/>" %}

参考 Q2，用 decode - encode 的方式写，不做逆序。

{% content-ref url="2.-add-two-numbers" %}
[2.-add-two-numbers](https://xuqiangwen1994.gitbook.io/practice/2.-add-two-numbers)
{% endcontent-ref %}

### 12/30/2020 Update:

把两个**左对称**的 linked list 变成**右对称** ----> 可以用 stack，last in first out

两个 stack 加起来变回 linked list 的方法也不简单，注意 residual 和对 next 指针的处理。

{% tabs %}
{% tab title="decode (no reverse)" %}

```python
# 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: ListNode, l2: ListNode) -> ListNode:
        return self.encode(self.decode(l1) + self.decode(l2))
    
    def decode(self, node):
        number = 0
        while node:
            number *= 10
            number += node.val
            node = node.next
        return number
            
    def encode(self, number):
        tail = None
        if number == 0: return ListNode(0)
        while number:
            number, m = divmod(number, 10)
            cur = ListNode(m)
            cur.next = tail
            tail = cur
        return tail
```

{% endtab %}

{% tab title="stack" %}

```python
# 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: ListNode, l2: ListNode) -> ListNode:
        s1, s2 = [], []
        while l1:
            s1.append(l1.val)
            l1 = l1.next
        while l2:
            s2.append(l2.val)
            l2 = l2.next
        
        residual = 0
        prev = None
        
        while s1 or s2 or residual:
            n1 = s1.pop() if s1 else 0
            n2 = s2.pop() if s2 else 0
            number = n1 + n2 + residual
            residual, number = divmod(number, 10)
            curr = ListNode(number)
            curr.next = prev
            prev = curr
            
        return prev
            
            
            
```

{% endtab %}
{% endtabs %}
