2、两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807

第一种方法

自己没看答案前，自己想的方法，比较笨的方法。
简单来说就算将链表转成字符串，再转成数字，相加过后，再最终转成链表。

def addTwoNumbers1(l1, l2):
    """自己的原始方法，时间复杂度不是最优的"""
    # 将链表转为字符串
    str1 = ""
    str2 = ""
    while l1 is not None:
        str1 = str(l1.val) + str1
        l1 = l1.next

    while l2 is not None:
        str2 = str(l2.val) + str2
        l2 = l2.next

    sumStr = str(int(str1) + int(str2))
    # 将字符串转化为单向链表
    for i, value in enumerate(sumStr):
        print(i, value)
        if i == 0:
            l = ListNode(value)
        else:
            l = ListNode(value, l)
    return l

第二种方法

参考力扣官方答案和精选答案过后的做法。
简单来说，就算用一个链表用于记录结果。依次让两个链表的值相加，如果相加的和大于10，则进一位，并在下次的下一位的相加过程中加1。如果加到最后还是有进位，则再以1创建一个新的节点，赋值给next。
代码注释写的比较详细，代码如下：

def addTwoNumbers2(l1, l2):
    """参考力扣精选答案的做法"""
    # 用于存放结果的链表
    head = ListNode()
    # 移动指针
    h = head
    # 记录相加的和
    sum = 0
    # 记录是否进位的标志，开始默认是False
    carry = False
    while l1 != None or l2 != None:
        # 每次循环需要将sum重新置为0
        sum = 0
        if l1 != None:
            # 加上链表的对应值
            sum += l1.val
            # 将l1指向下一个子节点
            l1 = l1.next

        if l2 != None:
            sum += l2.val
            l2 = l2.next
        # 如果进位标志为True，则加1
        if carry:
            sum += 1

        # sum%10 表示这位应该显示的数字，比如说如果相加结果是13，则这一位应该显示的是3，然后向前进1位
        # 并且以 sum%10 这位应该显示的数字，创建一个新的节点，赋值给存储链表的下一个节点
        h.next = ListNode(sum%10)
        # 将指针移动到下一个节点
        h = h.next
        # 如果 sum大于等于10，说明有进位，将carry标记为True，方便下次计算的将进位的1加上
        carry = True if sum >= 10 else False

    # 如果循环结束了，进位标志还是为True，则还应该进1位，也就是以1创建一个子节点，赋值给next
    if carry:
        h.next = ListNode(1)

    # 是从head的next开始记录相加的值，所以返回head.next链表
    return head.next

第三种方法

这种方法是参考的九章算法的精选答案。和第二种方法原理是一样的，只是写法更加精简。

def addTwoNumbers3(l1, l2):
    """参考九章算法答案的做法"""
    # 用于存放结果的链表
    head = ListNode()
    # 移动指针
    ptr = head
    # 用于记录相加的结果
    carry = 0
    while True:
        if l1 != None:
            carry += l1.val
            l1 = l1.next
        if l2 != None:
            carry += l2.val
            l2 = l2.next

        # carry%10 表示这位应该显示的数字，比如说如果相加结果是13，则这一位应该显示的是3
        # 并且将 carry%10 这位应该显示的数字，存储在本节点
        ptr.val = carry % 10
        # carry /= 10 大于0 表示有进位，并且carry就等于1了，直接用于下一次的相加运算(也就是说已经把进位算在里面了)
        # 如果carry = 13，那么carry /= 10 就等于1，直接用于下一次相加就把进位的1算在里面了
        carry = int(carry / 10)
        # 运算未结束新建一个节点用于储存答案，否则退出循环
        # 当carry等于0时，表示已经最高位都已经加完了，所以退出循环
        if l1 != None or l2 != None or carry != 0:
            ptr.next = ListNode()
            ptr = ptr.next
        else:
            break

    return head

复杂度分析

后面两种方法的复杂度如下：

• 时间复杂度：O(max(m,n))，其中 m,n 为两个链表的长度。我们要
  遍历两个链表的全部位置，而处理每个位置只需要O(1)的时间。
• 空间复杂度：O(max(m,n))，答案链表的长度最多为较长链表的长度 +1。