力扣题（2）—— 两数相加

两数相加

题目内容

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例

示例 1：

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

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/add-two-numbers

题解一：暴力解法

根据示例的解释，最先想到的方法就是将链表转为数字，然后数字相加再翻转，最后生成新链表。

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    	# 循环输出 l1 链表的数字添加到列表中
        l1_list = []
        while True:
            if l1 is None:
                break
            l1_list.append(l1.val)
            l1 = l1.next
		
		# 循环输出 l2 链表的数字添加到列表中
        l2_list = []
        while True:
            if l2 is None:
                break
            l2_list.append(l2.val)
            l2 = l2.next
		
		# 将 l1 列表中的数字连接形成字符串
        a = ""
        for i in l1_list:
            a += str(i)
		
		# 将 l2 列表中的数字连接形成字符串
        b = ""
        for i in l2_list:
            b += str(i)
		
		# 将 l1 ，l2 形成的字符串翻转之后形成相加之后的数字
        c = int(a[::-1]) + int(b[::-1])

        c = str(c) # 数字转换为字符串

		# 翻转最后的字符串，循环形成新的链表
        for i in range(0, len(c)):
            if i == 0:
                res = ListNode(val = int(c[i]), next = None)
            else:
                res = ListNode(val = int(c[i]), next = res)

        return res

力扣通过的时间大约是104 ms

题解二

根据示例一可以发现其实这是一个从最高位向最低位运算的竖式运算，并且根据示例三可以发现题目的竖式计算是最高位对齐的竖式计算。

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    	# 循环输出 l1 链表的数字添加到列表中
        l1_list = []
        while True:
            if l1 is None:
                break
            l1_list.append(l1.val)
            l1 = l1.next
            
		# 循环输出 l2 链表的数字添加到列表中
        l2_list = []
        while True:
            if l2 is None:
                break
            l2_list.append(l2.val)
            l2 = l2.next

        res = []

        l1_length = len(l1_list)
        l2_length = len(l2_list)
        num_ten = 0
		
		# 考虑 l1 和 l2 链表不一样长的情况
        min_length = min(l1_length, l2_length)
        max_length = max(l1_length, l2_length)

        for i in range(0, min_length): # 尾（头部）对齐
            num = l1_list[i] + l2_list[i] + num_ten
            num_ten = num // 10 # 10位数上的数字,即需要进位的数字
            num_one = num % 10 # 个位数上的数字

            res.append(num_one) # 根据竖式运算法则，保留个位数字，十位数进位

        for i in range(min_length, max_length): # 长出的部分进行进位
            if l1_length > min_length:
                num = l1_list[i] + num_ten
                num_ten = num // 10 # 10位数上的数字
                num_one = num % 10 # 个位数上的数字

                res.append(num_one)
            elif l2_length > min_length:
                num = l2_list[i] + num_ten
                num_ten = num // 10 # 10位数上的数字
                num_one = num % 10 # 个位数上的数字

                res.append(num_one)
        
        if num_ten != 0:
            res.append(num_ten)
		
		# 翻转并形成链表
        res = res[::-1]

        for i in range(0, len(res)):
            if i == 0:
                ans = ListNode(val = int(res[i]), next = None)
            else:
                ans = ListNode(val = int(res[i]), next = ans)

        return ans

力扣通过的时间大约是56 ms