The topic of dry

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.

Advanced:

What if the input linked list cannot be modified? In other words, you can’t flip the nodes in the list.

Example:

Input: (7 - > 4 - > 2 - > 3) + (5 - > 6 - > 4) output: 7-8 - > > 0 - > 7Copy the code

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.

Method: the stack

The difference between this problem and adding two numbers is that adding two numbers reverses the order of the numbers for us, so we can directly manipulate lists to do similar vertical operations, we just have to deal with the logic of the calculation. This problem gives us the initial data, so we should convert them to a computable form. Then we need to think of another data structure, the stack. We push the data of the two linked lists on the stack, and then calculate the top of the stack, and then we can get the result we want.

It is also important to note that we compute the results from back to front, so instead of storing the results in a regular linked list, we use a header insertion method, with each insertion following the next node in the head. So that guarantees the order of our results.

Code implementation:

/** * 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}* /
var addTwoNumbers = function (l1, l2) {
    let stack1 = [];
    let stack2 = [];
    while(l1 ! =null) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while(l2 ! =null) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    let newListNode = new ListNode(0);
    let current = newListNode;
    let yu = 0;
    let zhi = 0;
    while (stack1.length > 0 && stack2.length > 0) {
        let stack1data = stack1.pop();
        let stack2data = stack2.pop();
        zhi = (stack1data + stack2data + yu) % 10;
        headInsertToList(current, zhi)
        yu = Math.floor((stack1data + stack2data + yu) / 10);
    }
    if(stack1.length ! =0) {
        while(stack1.length ! =0) {
            let stack1data = stack1.pop();
            zhi = (stack1data + yu) % 10;
            headInsertToList(current, zhi)
            yu = Math.floor((stack1data + yu) / 10); }}if(stack2.length ! =0) {
        while(stack2.length ! =0) {
            let stack2data = stack2.pop();
            zhi = (stack2data + yu) % 10;
            headInsertToList(current, zhi)
            yu = Math.floor((stack2data + yu) / 10); }}if(yu ! =0) {
        headInsertToList(current, yu)
    }
    return newListNode.next
};
function headInsertToList(current, zhi) {
    let newNode = new ListNode(zhi)
    newNode.next = current.next;
    current.next = newNode
}
Copy the code