# LeetCode: 445. Add Two Numbers II

## 题目¶

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

```Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
```

## 解法¶

### 反向遍历链表然后按照加法运算的规则计算各个节点的值¶

• 因为是单向链表无法快速反向遍历，可以通过正向遍历链表生成一个节点组成的栈，然后通过栈来实现反向遍历的需求。
• 因为是从低位到高位进行计算，所以结果也是从低位开始生成的，因此这里需要反向生成结果链表。

```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
stack1 = []
stack2 = []
while l1 is not None:
stack1.append(l1)
l1 = l1.next
while l2 is not None:
stack2.append(l2)
l2 = l2.next

carry = 0
while stack1 or stack2 or carry > 0:
l1_val = 0
l2_val = 0
if stack1:
l1_val = stack1.pop().val
if stack2:
l2_val = stack2.pop().val

total = l1_val + l2_val + carry
carry = total // 10
val = total % 10
node = ListNode(val)