[数据结构与算法]LeetCode第二题，两数相加

题目

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

?解题

解法一：老实人

? ? ? ? （抛开ListNode）将输入转换为整数，相加后返回成列表。

def addTwoNumbers(l1, l2):
    l1 = l1[::-1]
    l2 = l2[::-1]
    n1 = len(l1)
    n2 = len(l2)
    result1 = 0
    result2 = 0
    for i in l1:
        n1 -= 1
        result1 += i * pow(10, n1)
    for i in l2:
        n2 -= 1
        result2 += i * pow(10, n2) 
    result = result1 + result2
    result = list(str(result))
    a = []
    for i in result:
        a.append(int(i))
    return a[::-1]

? ? ? ? 然后就会发现，三个样例都没问题，你觉得你行了，但是你试试下面这个...

l1 = [1,0,0,1]
l2 = [1,0,1]
result = addTwoNumbers(l1, l2)
print(result)

? ? ? ? 结果就是那么不尽如人意了?，这就是这个方法的不足之处。

解法二：ListNode

? ? ? ? 首先看一下ListNode的定义：

struct ListNode {
       int val;    //定义val变量值，存储节点值
       struct ListNode *next;   //定义next指针，指向下一个节点，维持节点连接
  }

? ? ? ? 然后看一下代码实现：

def addTwoNumbers(l1, l2):
    head = ListNode(l1.val + l2.val) #val是这个节点的值，next是指向下一节点的指针
    cur = head # cur表示当前节点
    while l1.next or l2.next: # 遍历l1和l2
        l1 = l1.next if l1.next else ListNode()
        l2 = l2.next if l2.next else ListNode()
        cur.next = ListNode(l1.val + l2.val + cur.val // 10) # 有无进位
        cur.val = cur.val % 10
        cur = cur.next
    if cur.val >= 10: # 最后一位有无进位
        cur.next = ListNode(cur.val // 10)
        cur.val = cur.val % 10
    return head

? ? ? ? 可以放到LeetCode上面跑，想在VScode上面运行的话，会显示'ListNode' is not defined的错误，可以参考https://leetcode-cn.com/circle/article/s3RcOW/尝试解决。