2.add two numbers

题目要求

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

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

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

题解

 /**
  * Definition for singly-linked list.
  * public class ListNode {
  *     int val;
  *     ListNode next;
  *     ListNode(int x) { val = x; }
  * }
  */
 class Solution {
     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
         ListNode list = new ListNode(0);
         ListNode head = list;
         int can = 0;
         while(l1!=null||l2!=null||can!=0){
            int l1Val = l1 !=null ? l1.val:0;
            int l2Val = l2 !=null ? l2.val:0;
            int temp = l1Val+l2Val+can;
            int quyu = temp%10;
            if(temp-10 >= 0){
                can = 1;
            }else{
                can = 0;
            }
            ListNode tempNode = new ListNode(quyu);
            head.next=tempNode;
            head=tempNode;
            if(l1!=null)l1 = l1.next;
            if(l2!=null)l2 = l2.next;
         }
         return list.next;
     }
 }

/**
  * 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) {
     var list = new ListNode(0);
     var head = list;
     let i = 0;
     while(l1||l2||i!=0){
         var l1Val = l1 ? l1.val:0;
         var l2Val = l2 ? l2.val:0;
         var sum = l1Val+l2Val+i;
         if(sum>9){
             i = 1;
             var final = sum - 10;
         }else{
             i = 0;
             var final = sum;
         }
         var temp = new ListNode(final);
         head.next = temp;
         head = head.next;
         if(l1){l1 = l1.next}
         if(l2){l2 = l2.next}
     }
     return list.next;
 };

分析

总体不难（尽管标注为中等），核心是单链表的尾插法。

我用了两种语言java和javascript按同一思路进行实现，对比如下:

	java	javascript
耗时	2ms（99.90%）	144ms（39.55%）
内存消耗	40.1mb（17.28%）	42.9mb（96.98%）

通过以上表格可以发现在一定条件下服务端语言在效率上会明显好于脚本语言，当然在本例中JavaScript并不是最优解(但我感觉差不多的....)。

还有要注意一点的是：

 # 在编程语言中使用四则运算中
 # 最消耗时间是除法、取余这类操作
 # 其次是乘法
 # 最后是加减法
 # 当然 位运算 是最快的（也是最难掌握的）。
 # 来源：https://blog.csdn.net/morgerton/article/details/64918560

复习

尾插法

 /**
  * 链表节点
  */
 public class ListNode {
     int val;
     ListNode next;
     public ListNode(int val){
         this.val = val;
     }
 }
 ​
 /**
  * 方法
  */
 class InsertNode{
 ​
     /**
      * 尾插法：
      * 将后建立的结点插在链表尾部，
      * 这种方法建立起来的链表的实际顺序与输入顺序相同，
      * 在对链表顺序有严格要求时，
      * 建议使用尾插法！
      * 尾插法有多种实现
      * 其核心为：
      *
      * 新节点链接到链表尾部
      * 尾部永远指向链表最末端
      *
      * （本题完美匹配：输入为倒序，输出为正序）
      * @param head 链表
      * @param val 插入节点值
      * @return
      */
     public ListNode WeiInsert(ListNode head , int val){
         //1.要插入的值
         ListNode insertNode = new ListNode(val);
 ​
         //2.必须创建一个节点指向链表的最后一个节点(tailor:尾巴)
         ListNode tailor = head;
 ​
         //3.判断头结点是否为空，空的话，将头指向第一个节点
         if(head==null){
              head =  insertNode;
         }else {
             //4. 如果不为空
 ​
             //4.1 将尾巴指向链表最后一个位置
             while (tailor.next!=null){
                 tailor = tailor.next;
             }
 ​
             //4.2 在尾巴的下一个位置插入新节点
             tailor.next = insertNode;
             
 ​
         }
         return head;
     }
 }