# The sum of two numbers [of moderate difficulty]

Topics

Two non-empty linked lists are given to represent two non-negative integers. Among them, their respective digits are stored in reverse order, and each of their nodes can only store one digit.

If we add the two numbers together, we return a new list to represent their sum.

You can assume that neither of these numbers will begin with zero except the number 0.

Examples:

```Input: (2 - > 4 - > 3) + (5 - > 6 - > 4)
Output: 7 - > 0 - > 8
Cause: 342 + 465 = 807```

Source: LeetCode

1. Algorithmic ideas

It's a question of storing numbers in a linked list and adding them up. It's not difficult. According to personal thinking, there are two ways to learn from:

 Add each other one by one, add each one first, put the flag generated by carry, and then add 10 bits to add flag, and then empty the flag after adding flag. It is worth noting that some boundary problems need to be handled carefully.

 Conversion and addition, Java provides BigInteger, no matter how large integers can be added, the idea is to convert the list into a string (pay attention to reverse), and then into BigInteger, after the addition can be converted back, very simple.

2. Code

 JAVA implementation:

``````    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;  //Grasp the penultimate
listNode = listNode.next;
}
if(daoshudier.next.val == 0){
daoshudier.next = null;
}
return p;
}``````

 Python implementation:

``````class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
'''
:param l1: Chain 1
:param l2: List 2
'''
listNode = ListNode(0)
rsp = listNode
daoshudier = listNode   # This pointer points to the penultimate node
p = l1
length = 0  # Length of linked list
length1 = 0
length2 = 0
flag = 0    # Carry mark, the sum of two digits, the result will not exceed two digits
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
# Pre-return judgment
return rsp

def getGeWei(self, num: int):
'''
//Get two-digit digits
: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):
'''
//Get ten digits of two digits
:param num:
:return:
'''
if num > 99:
return None
if num < 10 and num >= 0:   # There are no ten digits in a single digit. Ten digits are zero.
return 0
elif num > 9 and num <= 99:
return int(list(str(num)).pop(0))``````

3. Operation results Figure 1 - JAVA code execution results (the fastest 2 ms in the submission record, Tian Na) Figure 2 - Python execution results

4. Summary

Using JAVA and Python two languages to write a simple algorithm, but the problem arises, JAVA execution 23ms in the analysis diagram did not appear, meaning that I write this JAVA code poorly. If you follow the Python set to use JAVA writing efficiency should be higher, but I have to lament that JAVA is more flexible than Python, there are many can be optimized.

After several days of writing, let me understand that the general algorithm problem is not difficult, but flexibility is really true. Over the past few days, I have a further understanding of debugging, and I have another idea about code optimization. Come on. Make persistent efforts

Posted on Wed, 04 Sep 2019 21:16:52 -0700 by monkuar