# [中等难度]两数相加

2019/09/05 10:37

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)

1. 算法思路

[1] 逐位相加，先加各位，进位产生的放到flag；然后十位相加在加上flag，加完flag要清空；依次加..... 值得注意的是有些边界问题需要小心处理。

[2] 转换相加法，Java提供BigInteger，无论多大的整数都可以相加，思路就是将链表转换成字符串(要注意reverse)，进而转换成BigInteger,加完后转换回来即可，挺简单的。

2. 代码

[1] JAVA实现：

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode listNode = new ListNode(0);
ListNode p = listNode;
ListNode daoshudier = listNode;
StringBuilder numStr1 = new StringBuilder();
StringBuilder numStr2 = new StringBuilder();

while (l1 != null){
numStr1.append(l1.val);
l1 = l1.next;
}
while (l2 != null){
numStr2.append(l2.val);
l2 = l2.next;
}
numStr1.reverse();
numStr2.reverse();

BigInteger num1 = new BigInteger(numStr1.toString());
BigInteger num2 = new BigInteger(numStr2.toString());

String ans = ansTmp.toString();

for(int i = ans.length() - 1; i > -1; i--){
listNode.val = (int)ans.charAt(i) - 48;
listNode.next = new ListNode(0);
daoshudier = listNode;  //抓稳倒数第二个
listNode = listNode.next;
}
if(daoshudier.next.val == 0){
daoshudier.next = null;
}
return p;
}

[2] Python实现：

class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
'''
计算两个链表相加的和
:param l1: 链表1
:param l2: 链表2
:return: 两个链表相加后的结果
'''
listNode = ListNode(0)
rsp = listNode
daoshudier = listNode   # 该指针指向倒数第二个节点
p = l1
length = 0  # 链表的长度
length1 = 0
length2 = 0
flag = 0    # 进位的标志，两个个位数字相加，结果不会超过两位数
while p != None:
length1 += 1
p = p.next
p = l2
while p != None:
length2 += 1
p = p.next
if length1 > length2:
length = length1
else:
length = length2

for i in range(length):
if l1 != None and l1.val != None:
tmp1 = l1.val
else:
tmp1 = 0
if l2 != None and l2.val != None:
tmp2 = l2.val
else:
tmp2 = 0
rs = tmp1 + tmp2 + flag
listNode.val = self.getGeWei(rs)
listNode.next = ListNode(0)
daoshudier = listNode
listNode = listNode.next
flag = self.getShiWei(rs)
if l1 != None:
l1 = l1.next
if l2 != None:
l2 = l2.next
listNode.val += flag
if listNode.val == 0:
daoshudier.val += flag
if daoshudier.val > 9:
listNode.val = self.getShiWei(daoshudier.val)
else:
daoshudier.next = None
# 返回前判断
return rsp

def getGeWei(self, num: int):
'''
获得二位数的个位数字
:param num:
:return:
'''
if num > 99:
return None
if num < 10 and num >= 0:
return num
elif num > 9 and num <= 99:
return int(list(str(num)).pop(-1))

def getShiWei(self, num: int):
'''
获得二位数字的十位数字
:param num:
:return:
'''
if num > 99:
return None
if num < 10 and num >= 0:   # 个位数字是没有十位的，十位为0
return 0
elif num > 9 and num <= 99:
return int(list(str(num)).pop(0))

3.运行结果

4.总结

0
0 收藏

0 评论
0 收藏
0