Topic describes

You are given two non-empty linked lists to represent two non-negative integers. The highest digit is at the beginning of the list. They store only one digit per node. Adding the two numbers returns a new linked list.

You can assume that neither of these numbers will start with zero, except for the number zero.

 

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4] output: [7,8,0,7] example 2:

Input: l1 = [2,4,3], l2 = [5,6,4] output: [8,0,7] example 3:

Input: L1 = [0], L2 = [0] Output: [0]

Tip:

The length range of the linked list is [1, 100] 0 <= node.val <= 9 Input data Ensure that the number represented in the linked list does not have a leading 0

Source: LeetCode link: leetcode-cn.com/problems/ad… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Antithesis thought

  1. Ontology is to see the ends of two lists as the ones place of two numbers, followed by ten, hundreds, thousands…
  2. Since the list starts at the head, the calculation should start at the tail and add up and carry up to 10.
  3. We’re going to start with the guys and we’re going to flip the lists and add them up bit by bit.
  4. Finally, the calculation result is reversed again for the answer.

Answer key code

* @lc code= leetcode.cn id=445 lang=javascript ** [445] Two number add II */ // @lc code=start /** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : Next) *} */ /** * @param {ListNode} L1 * @param {ListNode} l2 * @return {ListNode} */ / reverse a list var reverseList = function(head){ let pre = null,cur = head; while (cur) { let next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; If (l1.val === 0) return l1.val === 0; if(l2.val === 0) return l1; RevL1 = reverseList(L1),revL2 = reverseList(l2); let sumList = new ListNode(0); // define a new list whose head is 0 let sumNode = sumList; // let carry = 0; / / carry flag while (revL1 | | revL2) {/ / to make two lists from bits, plus numerical let carry sum = (revL1 = = = null? 0 : revL1.val) + (revL2 === null? 0 : revL2.val) + carry; If (sum >= 10){carry = 1; if(sum >= 10){carry = 1; sum -= 10; }else{ carry = 0; } let newNode = new ListNode(sum); sumNode.next = newNode; // Make the next value of the new list point to the current calculated value sumNode = sumnode.next; // Move pointer to next node revL1 = revL1 == null? null : revL1.next; revL2 = revL2 == null ? null : revL2.next; If (carry > 0) sumNode. Next = new ListNode(carry); if(carry > 0) sumNode. Return reverseList(sumlist.next)}; return reverseList(sumlist.next)}; // @lc code=endCopy the code