两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-zxhnext-ixs1/

思路：

1.新建一个空链表；

2.遍历被相加的两个链表，如果一个链表先结束，后面位数都补0;

3.模拟相加操作，将个位数追加到新链表上，十位数留到下一位相加；

var addTwoNumbers = function(l1, l2) {
	// 新建一个空链表
     let newList = new ListNode(0);
     let p1 = l1,p2 = l2;
     // 链表赋值给临时变量，初始化存储进位
     let cur = newList, carry = 0;
     // 当链表不为空的时候
     while(p1 || p2){
         // 如果链表遍历未结束，取出链表中的值赋值给v1 ,否则补0
         let v1 = p1 ? p1.val : 0;
         let v2 = p2 ? p2.val : 0;
         // 求和，包含存储进位
         let val = v1 + v2 + carry;
         // 个位数取整，并追加到链表上
         carry = ~~(val / 10);
         // 十位数留到下一位相加
         cur.next = new ListNode(val % 10);
         // 如果链表还有值，继续遍历
         if(p1) p1 = p1.next;
         if(p2) p2 = p2.next;
         cur = cur.next;
     }
     // 如果没有进位，追加到最后
     if(carry) {
         cur.next = new ListNode(carry);
     }
     return newList.next;
}

时间复杂度O(n),空间复杂度o(1)