问题描述：https://leetcode.com/problems/add-two-numbers/
思路1：基本加法规则
根据小学学的基本加法规则。。。。。我们需要将两个数以最低位为基准对齐，然后逐个加，需要进位的给进位就行了。。。。恰好这个链表是逆序的！！！已经为我们对齐了。用两个指针分别指向两个链表头，开始同步往后移动，边移动边计算结果，直到两个指针都到了尽头/没有进位。时间复杂度是O(max(m, n))，空间复杂度和时间复杂度一样。js代码如下：
// Runtime: 116 msvar addTwoNumbers = function(l1, l2) { ???let dummy = { next: null }, // 结果链表的head指针 ???????tail = dummy, // tail总是指向dummy的末尾元素,以便在链表尾插入新元素 ???????flag = false, // flag标示是否需要进位 ???????sum; ???let init = () => { // 初始化,因为保证非空,所以首位总是存在的(可能为0) ???????sum = l1.val + l2.val; ???????tail.next = new ListNode(sum % 10); ???????// 为下一位的计算做准备 ???????flag = sum >= 10; ???????l1 = l1.next; ???????l2 = l2.next; ???????// 保持tail性质不变 ???????tail = tail.next; ???}; ???let work = () => { ???????let v1, v2; ???????while (l1 || l2 || flag) { ???????????// 统一化处理,不用判断谁空谁不空 ???????????v1 = l1 ? l1.val : 0; ???????????v2 = l2 ? l2.val : 0; ???????????sum = v1 + v2 + (flag ? 1 : 0); ???????????tail.next = new ListNode(sum % 10); ???????????// 为下一位的计算做准备 ???????????flag = sum >= 10; ???????????l1 = l1 ? l1.next : null; ???????????l2 = l2 ? l2.next : null; ???????????// 保持tail性质不变 ???????????tail = tail.next; ???????} ???}; ???init(); ???work(); ???return dummy.next;};思路2：移花接木法。。。
基本上和思路1没区别，并不能改善时间复杂度的渐进性，只是省了点空间。js代码：
// 不创建新链表,直接把结果存到l1上,并对多出来的部分做"嫁接"处理// Runtime: 112 ms, faster than 99.52% of JavaScript online submissions for Add Two Numbers.var addTwoNumbers2 = function(l1, l2) { ???let dummy = { next: l1 }, // 结果链表的head指针 ???????tail = dummy, // tail总是指向l1的前继元素(也就是dummy的尾元素)，以便在链尾插入链表/新元素 ???????flag = false, // flag标示下一位的计算是否需要进位 ???????sum; ???let init = () => { // 初始化,因为保证非空,所以首位总是存在的 ???????sum = l1.val + l2.val; ???????l1.val = sum % 10; ???????// 为下一位的计算做准备 ???????flag = sum >= 10; ???????l1 = l1.next; ???????l2 = l2.next; ???????// 保持tail性质不变 ???????tail = tail.next; ???}; ???let status1 = () => { // 处理等长的那部分 ???????while (l1 && l2) { ???????????sum = l1.val + l2.val + (flag ? 1 : 0); ???????????l1.val = sum % 10; ???????????// 为下一位的计算做准备 ???????????flag = sum >= 10; ???????????l1 = l1.next; ???????????l2 = l2.next; ???????????// 保持tail性质不变 ???????????tail = tail.next; ???????} ???}; ???let status2 = () => { // 处理多出来的部分 ???????// 如果l2更长,直接移植到l1 ???????if (l2) { ???????????l1 = tail.next = l2; ???????} ???????// 处理进位 ???????while (l1 && flag) { ???????????sum = l1.val + 1; ???????????l1.val = sum % 10; ???????????// 为下一位的计算做准备 ???????????flag = sum >= 10; ???????????l1 = l1.next; ???????????// 保持tail性质不变 ???????????tail = tail.next; ???????} ???????if (flag) { ???????????tail.next = new ListNode(1); ???????} ???}; ???init(); ???status1(); ???status2(); ???return dummy.next;};LeetCode #002# Add Two Numbers（js描述）
原文地址：https://www.cnblogs.com/xkxf/p/10226056.html