[B] [C] [D]

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

Advanced: What if the input list cannot be flipped?

Add the numbers represented by the input string and return the resulting list with the highest digit stored in the head node

And since the problem requires that we do not flip the list to complete the problem, we can use the stack to store the values of each node in the list

Since the head node of the input list stores the value of the highest digit corresponding to it, and the stack is an advanced and outgoing data structure, the last value at the top of the stack corresponds to the value of the one digit

In this way, when the two top elements of the stack are taken out initially, the values corresponding to the units digit of the two numbers in the input linked list are added together, and the units digit of the corresponding numbers and values in the input linked list can be determined according to the sum value. By analogy, the values of each digit of the two input numbers and values can be determined

The result linked list is built from the value of each bit

The solution is as follows:

1. Create two stacks, initialized as empty arrays, that store the values of each node input to the linked list
2. Iterate through the input linked list, placing each node’s`val`Push into the corresponding stack
3. Add the top elements of two stacks each time, and determine the current digit of the sum of two numbers corresponding to the input linked list according to the value of and. The thing to notice is that the sum is greater than or equal to`10`Need to record the carry number
4. Construct the result list based on the current digit. Note that the problem requires the highest digit in the result list to be located at the head of the list, and the initial value is a digit, then tens, hundreds… , so the result list needs to be built in reverse order
5. Finally, when both stacks are empty, we need to determine whether the carry value is`0`, if the carry value is not`0`, you need to create nodes based on carry values and join them at the beginning of the result list

The overall process is as follows:

The code is as follows:

``Var addTwoNumbers = function(l1, l2) {const stack1 = [], stack2 = []; while(l1){ stack1.push(l1.val); l1 = l1.next; } while(l2){ stack2.push(l2.val); l2 = l2.next; } // let carry = 0, res = null; // Add the two numbers and build the resulting list based on the values of the sum. // Because the resulting list requires the highest number to be at the head of the list, the following procedure results in the number from the lowest to the highest. So the build results list to reverse the process of constructing the while (determined by the length | | stack2. Length) {const sum = (walks. Pop () | | 0) + (stack2. Pop () | | 0) + carry; const node = new ListNode(sum%10); carry = Math.floor(sum/10); node.next = res; res = node; } if(carry){ const node = new ListNode(carry); node.next = res; res = node; } return res; };Copy the code``

So we’re done with leetcode-leetcode-445- add two numbers II