欢迎跟着夏老师一起学习算法，这方面我自己的基础很薄弱，所以解题方法和思路也会讲的很”小白“，不需要什么基础就能看懂。

关注公众号可以进行交流和加入微信群，群内定期有系列文章分享噢！

Question

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

分析

遍历两个链表把值加起来好之后插入链表，如果有进位的话需要把进位的值保存到后面的节点上，如果遍历完毕之后还剩下需要进位的值，那么需要插入末尾新节点。

边界情况

遇到链表相关的题目时一定要处理好边界情况，因为有些为空的链表或者只有 1 个节点的链表没有处理的必要，及时返回可以降低算法复杂度。

1. 链表 1 和链表 2 同时为空，直接返回 undefined 即可
2. 链表 1 为空，返回链表 2
3. 链表 2 为空，返回链表 1

解题方法

// 链表节点定义
function ListNode(val) {
  this.val = val;
  this.next = null;
}

function addTwoNumbers(l1, l2) {if(!l1 && !l2) { // 链表 1 和链表 2 同时为空，无需任何处理
    return;
  }
  if(!l1) { // 链表 1 为空，直接返回链表 2
    return l2;
  }
  if(!l2) { // 链表 2 为空，直接返回链表 1
    return l1;
  }
  
  let carry = 0; // 进位值
  let head = new ListNode(0); // 链表头节点
  let p = head; // 链表移动指针
  
  while(l1 || l2 || carry > 0) { // l1 和 l2 虽然不会同时为空，但是存在 l1 和 l2 长度不一致的情况，这种也需要处理
    let sum = carry; // sum 为本节点的值，需要加上前一个节点的进位值
    if(l1) {
     sum += l1.val; // 把链表 1 当前节点的值加上
     l1 = l1.next; // 移动链表 1 指针
    }
    if(l2) {
      sum += l2.val;
      l2 = l2.next;
    }
    
    if(sum >= 10) { // 两个个位数相加最大值为 18，所以到下一个节点进位的最大值为 1
      carry = 1;
      sum -= 10; // 去掉十位，保留个位为节点最终值
    } else {carry = 0; // 相加之后和小于 10，不需要进位，清除进位数据，否则死循环}
    
    p.next = new ListNode(sum); // 插入新节点
    p = p.next; // 新链表指针后移
  }
  
  return head.next; // 头结点的值不是相加得到的，所以需要后移一个节点返回由两个链表加起来的结果
}

进位的处理搞清楚之后这道题就清楚了。

时间复杂度 O(max(l1.length, l2.length))

循环次数的根据链表 1 和链表 2 中长的那个链表来的，因为要保证两个链表的所有节点都被便利到

空间复杂度 O(max(l1,l2))

最终链表的节点数也是根据链表 1 和链表 2 中长的那个链表来的，因为要保证两个链表的所有节点都被便利到，如果最后有进位的话，结果链表的长度会比链表 1 和链表 2 中长的链表大小 +1。

结尾

这道题的难度是中等，但是摸清楚链表的基本操作之后，应该没什么问题就能解决。

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照  逆序  的方式存储的，并且它们的每个节点只能存储  一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

实现思路：

典型的链表遍历操作题，非常简单的指针操作，做题时注意考虑到边界条件判断即可。

1. 实例化结果链表 result；
2. 创建 3 个 Node 变量（代替指针）指向 被加数链表 的第二个节点（因为头节点在实例化 result 时已经操作过）以及 result 链表 的头节点；
3. 循环链表直至最长的链表遍历结束以及进制为 0；
4. 在循环内将节点值相加并操作 Node 变量指向下一个节点即可；

注：

1. 为了加快算法速度，取整时我放弃了 parseInt，转而使用位运算 ~~
2. 另一种思路是先创建一个空头节点作为 result 链表 的头节点，所有相加的操作都放在循环中，最后返回 result.next 即可。这种方法可以 AC，但由于多了一个空节点，在内存和性能上都稍差。

我的实现：

/**
 * 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 count = l1.val + l2.val
  let carry = ~~(count / 10)
  const result = new ListNode(count % 10)
  let currentNode1 = l1.next
  let currentNode2 = l2.next
  let currentNode3 = result
  while (currentNode1 || currentNode2 || carry) {
    let digit = carry
    if (currentNode1 && currentNode2) {
      digit += currentNode2.val + currentNode1.val
      currentNode1 = currentNode1.next
      currentNode2 = currentNode2.next
    } else if (currentNode1) {
      digit += currentNode1.val
      currentNode1 = currentNode1.next
    } else if (currentNode2) {
      digit += currentNode2.val
      currentNode2 = currentNode2.next
    }
    carry = ~~(digit / 10)
    currentNode3 = currentNode3.next = new ListNode(digit % 10)
  }
  return result
};

成绩

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例:

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

<!–more–>

我的垃圾思路

1. 这个题的话, 根据他们提供的 ListNode 类, 按部就班的做下去就是可行的
2. 首先逆序的数字相加, 对于代码来说刚好是正序的, 因为我们遍历链表时是从左往右的, 刚好也是先对个位, 十位, 千位这样的顺序依次相加执行, 所以和咱们平常的计算习惯并无太多差异
3. 遍历链表时, 个位与个位相加, 十位与十位相加 …<font color=grey size=3>(node1[0]与 node2[0]相加,node1[1]与 node2[1]相加....也 ` 就是索引相同的部分相加)</font>
4. 如果两个 node 的当前索引都不为 null, 那就m= 两数相加且要加上上次的进位 计算, 满 10 进 1, 所以当前索引保留m%10, 进位m/10, 若有其中一个为null, 则另一个只用加进位即可
5. 注意每次进入循环都要new 一个新的ListNode
6. 因为在代码开头已经 new 了ListNode , 所以最后取l3.next 即为结果

我的垃圾代码

package com.dasnnj.practice.medium;

/**
 * Description <p> TODO:
 * 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。* <p>
 * 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。* <p>
 * 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。* <p>
 * 示例：* <p>
 * 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
 * 输出：7 -> 0 -> 8
 * 原因：342 + 465 = 807
 * </p>
 *
 * @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a>
 * @date 2019-05-06 09:07
 */
public class TwoAdd {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode l3 = new ListNode(0);
        int m = 0;
        // 进位
        int n = 0;
        ListNode l = l3;
        while (l1 != null || l2 != null) {l.next = new ListNode(0);
            l = l.next;
            if (l1 == null) {
                // 则 l2 必然不为 null
                //                l.val = l2.val + n;
                m = l2.val + n;
            } else if (l2 == null) {
                // 则 l1 必然不为 null
                //                l.val = l1.val + n;
                m = l1.val + n;
            } else {m = (l1.val + l2.val) + n;
            }
            n = m / 10;
            if (n > 0) {
                l.val = m % 10;
                // 此步为了最后一个位置的两个数字加了之后需要进位
                l.next = new ListNode(n);
                //                l3.next.val = n;
            } else {l.val = m;}
            l1 = l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;

        }
        return l3.next;

    }

    public static void main(String[] args) {ListNode l1 = new ListNode(1);
        l1.next = new ListNode(8);
        l1.next.next = new ListNode(3);
        ListNode l2 = new ListNode(0);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(7);
        TwoAdd t = new TwoAdd();
        ListNode l3 = t.addTwoNumbers(l1, l2);
        System.out.println(l3);

    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {val = x;}

    @Override
    public String toString() {final StringBuilder sb = new StringBuilder("ListNode{");
        sb.append("val=").append(val);
        sb.append(", next=").append(next);
        sb.append('}');
        return sb.toString();}
}