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

Link: https://leetcode-cn.com/problems/add-two-numbers

II. Answer

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:

[1] 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.

[2] 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

[1] 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()); BigInteger ansTmp = num1.add(num2); 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; }`

[2] Python implementation:

`class Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: ''' //Calculate the sum of the additions of two linked lists :param l1: Chain 1 :param l2: List 2 :return: The results of the addition of two linked lists ''' 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