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