LeetCode 2. 两数相加(Add Two Numbers
2019-07-15 本文已影响0人
leacoder
LeetCode.jpg
2. 两数相加
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
切题
一、Clarification
1、明确题目
链表、非空、非负的整数、逆序、每个节点只能存储 一位 数字、除了数字 0 之外，不会以 0 开头
2、边界考虑
a、两个链表l1、l2，注意结束的判断
b、注意最高位进位后。进位位需要加入结果中
二、Possible Solution
1、迭代
借助哨兵节点，简化处理；
最高位进位单独处理；
循环遍历l1,l2，都结束时跳出循环，计算当前存储位cur_result，以及进位位next_add。
2、递归
由于存在进位，递归函数参数个数为3，包括l1,l2,add_num(进位位)
递归终止条件 l1,l2都为空并且add_num=0(没有进位)，这样将最高位进位的情况看成l1.val = 0 l2.val = 0进行统一处理
Python3
迭代
# @author:leacoder
# @des: 迭代——哨兵 两数相加
# 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:
pre1 = ListNode(None) # 哨兵
pre2 = ListNode(None)
pre1.next = l1
pre2.next = l2
# next_add进位位（cur_val_1+cur_val_2的十位数）, cur_val_1当前加数, cur_val_2当前被加数,
# cur_result当前存储位（cur_val_1+cur_val_2的个位数）
next_add, cur_val_1, cur_val_2, cur_result = 0, 0, 0, 0
result = ListNode(None)
head = result
while (pre1.next is not None) or (pre2.next is not None):
# 注意对于 next 是否为 None 的处理不同
if pre1.next is None:
cur_val_1 = 0
else:
cur_val_1 = pre1.next.val
pre1 = pre1.next
if pre2.next is None:
cur_val_2 = 0
else:
cur_val_2 = pre2.next.val
pre2 = pre2.next
val_sum = cur_val_1 + cur_val_2 + next_add
next_add = val_sum // 10
cur_result = val_sum % 10
node = ListNode(cur_result)
result.next = node
result = result.next
# 最高位进位处理
if next_add != 0:
node = ListNode(next_add)
result.next = node
return head.next
递归
# @author:leacoder
# @des: 递归+哨兵 两数相加
# 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:
return self.addNumbers(l1, l2, 0)
def addNumbers(self, l1: ListNode, l2: ListNode, add_num: int):
if l1 is None and l2 is None and add_num == 0: # 递归终止条件
return None
l1_value = l2_value = 0
if l1 is None:
l1_value = 0
else:
l1_value = l1.val
l1 = l1.next
if l2 is None:
l2_value = 0
else:
l2_value = l2.val
l2 = l2.next
sum_num = l1_value + l2_value + add_num
result = ListNode(sum_num % 10)
result.next = self.addNumbers(l1, l2, sum_num // 10)
return result
GitHub链接：
https://github.com/lichangke/LeetCode
个人Blog:
https://lichangke.github.io/
欢迎大家来一起交流学习
