445. Add two numbers II

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]Copy the code

Example 2:

Input: l1 = [2,4,3], l2 = [5,6,4]Copy the code

Example 3:

Input: L1 = [0], L2 = [0] Output: [0]Copy the code

Tip:

  • The length range of the linked list is [1, 100]
  • 0 <= node.val <= 9
  • Input data ensures that the linked list represents numbers without leading zeros

The thought of the stack

Train of thought

This problem we use the idea of stack to solve

Because we’re going to inherit one number from each list, and then we’re going to add them

  • First idea: just add numbers and then make lists

No. Because js can express a maximum of only a dozen digits, linked list long NAN

  • The thought of the stack

In addition, we have to start at the end, and if it’s greater than 10, we have to add one more digit, which affects the higher end

  • So we use two stacks stack1 and Stack2 to store the results of two linked list traversals
  • Then we iterate through both stacks again, as long as any one of them has a value, pop the last value from the end, which conforms to our rule of addition, and do the calculation. If >=10, we will advance by 1, use pre to hold the tens digit, and use curr to represent the ones digit
  • The numbers on the Pre must be reset after the calculation. Otherwise, the next calculation will be affected
  • Then we just need to use the plug method, one by one to put the newly generated nodes in front of the old node, to generate a new node
  • The pre may still have a value after the last walk, and the final node generation will take place

Returns the newly generated linked list

var addTwoNumbers = function (l1, l2) {
    var stack1 = []
    var stack2 = []
    var p1 = l1
    var p2 = l2
    while (p1) {
        stack1.push(p1.val)
        p1 = p1.next
    }
    
    while (p2) {
        stack2.push(p2.val)
        p2 = p2.next
    }
    var res = null
    var pre = 0
    var curr = 0
    while (stack1.length || stack2.length) {
        var pop1 = stack1.pop()
        var pop2 = stack2.pop()
        var num1 = pop1 ? pop1 * 1 : 0
        var num2 = pop2 ? pop2 * 1 : 0
        var total = pre ? num1 + num2 + pre : num1 + num2

        pre = 0
        if (total >= 10) {
            curr = total % 10
            pre = (total - curr) / 10
        } else {
            curr = total
        }
        var newHead = new ListNode(curr)
        newHead.next = res
        res = newHead
        curr = 0
    }
    if(pre){
        var newHead = new ListNode(pre)
        newHead.next = res
        res = newHead
    }
    return res
};
Copy the code