给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。 进阶：如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。 示例：输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)输出：7 -> 8 -> 0 -> 7

/* * @lc app=leetcode id=445 lang=javascript * * [445] Add Two Numbers II *//** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var addTwoNumbers = function (l1, l2) {  const stack1 = [];  const stack2 = [];  const stack = [];  let cur1 = l1;  let cur2 = l2;  let curried = 0;  while (cur1) {    stack1.push(cur1.val);    cur1 = cur1.next;  }  while (cur2) {    stack2.push(cur2.val);    cur2 = cur2.next;  }  let a = null;  let b = null;  while (stack1.length > 0 || stack2.length > 0) {    a = Number(stack1.pop()) || 0;    b = Number(stack2.pop()) || 0;    stack.push((a + b + curried) % 10);    if (a + b + curried >= 10) {      curried = 1;    } else {      curried = 0;    }  }  if (curried === 1) {    stack.push(1);  }  const dummy = {};  let current = dummy;  while (stack.length > 0) {    current.next = {      val: stack.pop(),      next: null,    };    current = current.next;  }  return dummy.next;};

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        auto carry = 0;        auto ret = (ListNode*)nullptr;        auto s1 = vector<int>();        toStack(l1, s1);        auto s2 = vector<int>();        toStack(l2, s2);        while (!s1.empty() || !s2.empty() || carry != 0) {            auto v1 = 0;            auto v2 = 0;            if (!s1.empty()) {                v1 = s1.back();                s1.pop_back();            }            if (!s2.empty()) {                v2 = s2.back();                s2.pop_back();            }            auto v = v1 + v2 + carry;            carry = v / 10;            auto tmp = new ListNode(v % 10);            tmp->next = ret;            ret = tmp;        }        return ret;    }private:    // 此处若返回而非传入vector，跑完所有测试用例多花8ms    void toStack(const ListNode* l, vector<int>& ret) {        while (l != nullptr) {            ret.push_back(l->val);            l = l->next;        }    }};// 逆置，相加，再逆置。跑完所有测试用例比第一种解法少花4msclass Solution {public:    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {        auto rl1 = reverseList(l1);        auto rl2 = reverseList(l2);        auto ret = add(rl1, rl2);        return reverseList(ret);    }private:    ListNode* reverseList(ListNode* head) {        ListNode* prev = NULL;        ListNode* cur = head;        ListNode* next = NULL;        while (cur != NULL) {            next = cur->next;            cur->next = prev;            prev = cur;            cur = next;        }        return prev;    }    ListNode* add(ListNode* l1, ListNode* l2) {        ListNode* ret = nullptr;        ListNode* cur = nullptr;        int carry = 0;        while (l1 != nullptr || l2 != nullptr || carry != 0) {            carry += (l1 == nullptr ? 0 : l1->val) + (l2 == nullptr ? 0 : l2->val);            auto temp = new ListNode(carry % 10);            carry /= 10;            if (ret == nullptr) {                ret = temp;                cur = ret;            }            else {                cur->next = temp;                cur = cur->next;            }            l1 = l1 == nullptr ? nullptr : l1->next;            l2 = l2 == nullptr ? nullptr : l2->next;        }        return ret;    }};

# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:        def listToStack(l: ListNode) -> list:            stack, c = [], l            while c:                stack.append(c.val)                c = c.next            return stack        # transfer l1 and l2 into stacks        stack1, stack2 = listToStack(l1), listToStack(l2)        # add stack1 and stack2        diff = abs(len(stack1) - len(stack2))        stack1 = ([0]*diff + stack1 if len(stack1) < len(stack2) else stack1)        stack2 = ([0]*diff + stack2 if len(stack2) < len(stack1) else stack2)        stack3 = [x + y for x, y in zip(stack1, stack2)]        # calculate carry for each item in stack3 and add one to the item before it        carry = 0        for i, val in enumerate(stack3[::-1]):            index = len(stack3) - i - 1            carry, stack3[index] = divmod(val + carry, 10)            if carry and index == 0:                stack3 = [1] + stack3            elif carry:                stack3[index - 1] += 1        # transfer stack3 to a linkedList        result = ListNode(0)        c = result        for item in stack3:            c.next = ListNode(item)            c = c.next        return result.next