给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

第一种「暴力解法」是分别遍历链表 L1 和 L2 ，然后把得到的结果相加，再创建新链表L3，当然了，想一想就好，一般暴力解法都容易超时。

第二种思路有些类似，就是在遍历链表的同时取值相加，唯一的难点就是在循环中使用同一个变量增加链表结点。这里取了个巧，给 head.next赋值，避免当前结点被覆盖。同时返回结果也是L3.next，链表可以看成一个嵌套的字典。

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        l3 = ListNode(0)
        head = l3
        step = 0
        while l1 or l2 :
            x = l1.val if l1 else 0
            y = l2.val if l2 else 0
            
            result = x + y + step
            step = result // 10
            
            head.next = ListNode(result % 10)
            head = head.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
        
        if step == 1:
            head.next = ListNode(1)
        
        return l3.next

注意进位以及结点为 None 的情况的校验。

值得一提的是注释部分只是提示链表的属性，如果取消注释是会报错的，在 LeetCode 上死活调试不过，被小坑了一把，囧。

虽然超过了100%的Python3提交，但是依然有优化的空间，算法优化的本身就是和自己较劲嘛 ^_^ 。

比如我们可以假设一种极端情况，就是其中 L2 长度远远大于 L1 ，例如：24 + 382847278173498112933718......，那么根据我们上面的算法，每次都要重新相加，耗时且消耗额外的内存。

优化的思路是，当判断到 L1 为 None 时，新链表的剩下的结点就是 L2 剩下的结点，只要让 head.next = L2.next就可以了，无需重新计算。当然了，L2 也可能为 None。代码的现有逻辑需要一些小变动，同时需要单独判断进位的情况。

具体实现待更 …