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

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

解题思路：在任一个链表只剩一个数或者两个链表都只剩一个数的时候，就单独来计算，判断是否产生进位。如果两个链表不等长，还需要再把较长的链表的后几位计算，判断是否产生进位。同样是计算到最后一位，再判断是否产生进位，是否需要链表扩容。

/**
* 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 cur1 = l1;
ListNode cur2 = l2;
int count = 0;//每位之和
int s = 0;//进位

while(cur1.next != null && cur2.next != null){//加到其中有一个链表剩一位，或者两个链表都只剩一位
count = cur1.val + cur2.val + s;
if(count > 9){
cur1.val = count % 10 ;
cur2.val = count % 10 ;
s = 1;
}else{
cur1.val = count;
cur2.val = count;
s = 0;
}
cur1 = cur1.next;
cur2 = cur2.next;

}

if(cur1.next == null && cur2.next == null){ //当两个链表都只剩一位时
count = cur1.val + cur2.val +s;
if(count > 9)
{
cur1.val = count % 10;
cur2.val = count % 10;
s = 1;
}else{
cur1.val = count ;
cur2.val = count ;
s = 0;
}
if(s == 1){ //说明最后两个数产生了进位，需要扩充链表。
ListNode tmp = new ListNode(1);
cur1.next = tmp;
return l1;
}
return l1;
}

if(cur1.next == null){ //cur1链表剩一位
count = cur1.val + cur2.val + s ;
cur2.val = cur1.val + cur2.val;
if(count < 10){ //cur1的最后一位加cur2的一位 没产生进位，直接返回
cur2.val = count;
return l2;
}
while(cur2.next != null){ //因为有进位，需要再把cur2的剩余数计算 直到最后一位
count = cur2.val + s;
if(count > 9){
cur2.val = count % 10 ;
s = 1;
} else{
cur2.val = count;
s = 0;
}
cur2 = cur2.next;
}
if(cur2.val + s > 9){ //判断cur2 最后一位是否产生进位
cur2.val = (cur2.val + s) % 10;
s = 1;
}else{
cur2.val = cur2.val +s;
s = 0;
}
if(s == 1){ //产生进位，扩充链表
ListNode tmp = new ListNode(1);
cur2.next = tmp;
return l2;
}
return l2;
}else{ //cur2链表剩一位
count = cur1.val + cur2.val + s;
cur1.val = cur2.val + cur1.val;
if(count < 10){ //cur2的最后一位加cur1的一位 没产生进位，直接返回
cur1.val = count;
return l1;
}
while(cur1.next != null){ //因为有进位，需要再把cur1的剩余数计算 直到最后一位
count = cur1.val + s;
if(count > 9){
cur1.val = count % 10 ;
s = 1;
} else{
cur1.val = count;
s = 0;
}
cur1 = cur1.next;
}
if(cur1.val + s > 9){ //判断cur1 最后一位是否产生进位
cur1.val = (cur1.val + s) % 10;
s = 1;
}else{
cur1.val = cur1.val +s;
s = 0;
}
if(s == 1){ //产生进位，扩充链表
ListNode tmp = new ListNode(1);
cur1.next = tmp;
return l1;
}
}
return l1;
}
}
————————————————

思路 在一个循环里 两个链表同时往下走
数据每位相加 可能有进位
加完新的链表也往下走

假设两个链表分别是:
[4,7,6] [9,1,8]

 

     674 + 819

     假如l1 = (4,7,6) l2 = (9,1,8)

         l1      =      4      7      6
         l2      =      9      1      8
        sum      =     13      8     14            和
       curr      =      3      8      4            当前位
  curr.next      =      1      0      1            进位 进位数值只可能为0或1
       sumX      =      3      9      4      1     进位加在后面 新数



和一般计算略有不同的是，需要把进位往右移。仅此而已

func addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -> ListNode? {
    //把当前节点初始化为哑节点
    let dummyHead = ListNode(0)
    //把p初始化为l1的头节点
    var p: ListNode? = l1
    //把q初始化为l2的头节点
    var q: ListNode? = l2
    //把起始节点(最后一个节点)初始化为哑节点
    //思路 每次curr要去获取下一个节点,但是上一个节点的值需要被保存起来
    //dummyHead是用来存储curr的 因为要操作curr去获取下一位 所以上一位必须被保存下来
    var curr: ListNode = dummyHead
    //进位默认为0
    var carry: Int = 0
    //只要有一个链表不为nil就进入循环
    while p != nil || q != nil {
        //如果l1的当前节点不为nil 取当前节点 如果为nil取0
        let x = (p != nil) ? p!.val : 0
        //如果l2的当前节点不为nil 取当前节点 如果为nil取0
        let y = (q != nil) ? q!.val : 0
        //求和
        //当前节点的数值相加并加上进位
        //(第一组数相加完才会有进位，所以第一组数的进位一定为0)
        let sum = carry + x + y
        //数字为一位还是两位 如果是一位 没有进位 如果是两位 有进位
        //一共10个数0->9
        carry = sum / 10
        //新链表当前节点的值为两个原链表当前节点的和除以10(进位)取余
        //(取后一位,因为可能有进位)
        curr.next = ListNode(sum % 10)
        //把下一个节点设置为当前节点
        curr = curr.next!
        //如果l1不为空 往下走查看下一个节点
        if p != nil { p = p!.next }
        //如果l2不为空 往下走查看下一个节点
        if q != nil { q = q!.next }
    }
    //如果carry不为0 则有进位(carry == 1) 把carry带入 直接把最右侧一个节点数值设置为1
    if carry > 0 {
        //curr是当前位 在循环结束后也是最后一位(不含进位)
        curr.next = ListNode(carry)
    }
    //返回链表
    return dummyHead.next;
}

1）方法实现1：
原理如下：原理：第一次给node挂上nextnode的时候，原理是当node开辟出一块内存的时候 temp也指向了node对应的这块内存，给temp的nextcode挂上节点以后，同时也就给node挂上了nextnode，第二次第三次给node挂节点的时候，再把temp指向temp的nextcode
————————————————

public static void main(String[] args) {
ChainNode node1 = new ChainNode(2);
ChainNode node1_1 = new ChainNode(4);
ChainNode node1_2 = new ChainNode(3);
node1.setNextNode(node1_1);
node1_1.setNextNode(node1_2);
ChainNode node2 = new ChainNode(5);
ChainNode node2_1 = new ChainNode(6);
ChainNode node2_2 = new ChainNode(4);
node2.setNextNode(node2_1);
node2_1.setNextNode(node2_2);
ChainNode node = TestAddTwoNumber.getNode(node1,node2);
while(null != node){
System.out.println(node.getVal());
node = node.getNextNode();
}

}

/***
* 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

原理：第一次给node挂上nextnode的时候，原理是当node开辟出一块内存的时候 temp也指向了node对应的这块内存，给temp的nextcode挂上节点以后，同时也就给node挂上了nextnode，
第二次第三次给node挂节点的时候，再把temp指向temp的nextcode
为了方便大家理解，我画了个原理图如下：
* @param args
*/
public static ChainNode getNode(ChainNode node1,ChainNode node2){
ChainNode node = new ChainNode(0);
ChainNode temp = node;
// ChainNode nodetemp = new ChainNode(0);
int carry = 0;//0 不进位 1 进位
while(node1 != null || node2 != null){
int x = node1.getVal();
int y = node2.getVal();
int sum = x + y + carry;
carry = sum / 10;
temp.setNextNode(new ChainNode(sum % 10));
temp = temp.getNextNode();
node1 = node1.getNextNode();
node2 = node2.getNextNode();
}
// node.setNextNode(nodetemp);
return node.getNextNode();
}
————————————————