[数据结构与算法]addTwoNumbers

题目：

?

?自己的思路：

刚开始做的是把链表每一位拼起来，形成num1，num2，再计算sum， 但是！对于短链表可以， t提示节点数在100以内，就算我把int-->long， long 类型的数据范围

?也肯定不够用，所以明显题目不是想让我们用这种方法。 而是应该采用 平时我们列竖式做运算，一样，先算个位。超过10进1位，逐步往高位算

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {   
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int curVal = l1.val + l2.val;   //新链表数据
        boolean flag = false;  //标志需不需要进位
        if((l1.val + l2.val) >= 10){  
            flag = true;
            curVal %= 10;      
        }
        ListNode temp = new ListNode(curVal);
        ListNode l = temp;
        ListNode temp1 = l1;
        ListNode temp2 = l2;    //其实这里temp1 和temp2 不必要，可以直接用l1、l2
        while (temp1.next !=null || temp2.next != null) {
            if (temp1.next != null && temp2.next != null) {
                //两个链表都还有数据,相加
                temp1 = temp1.next;
                temp2 = temp2.next;
                curVal = temp1.val + temp2.val;
                if(flag){
                    curVal += 1;
                    flag = false;
                }
                if(curVal >= 10){
                    //大于10需要进位
                    flag = true;
                    curVal %= 10;
                }
                temp.next = new ListNode(curVal);
                temp = temp.next;
            }else if(temp1.next != null){
                //l1还有数据，l2没有数据了
                temp1 = temp1.next;
                curVal = temp1.val;
                if(flag){
                    curVal += 1;
                    flag = false;
                }
                if(curVal >= 10){
                    //大于10需要进位
                    flag = true;
                    curVal %= 10;
                }
                temp.next = new ListNode(curVal);
                temp = temp.next;
            }else if(temp2.next != null) {
                //l2还有数据，l1没有数据了
                temp2 = temp2.next;
                curVal = temp2.val;
                if(flag){
                    curVal += 1;
                    flag = false;
                }
                if(curVal >= 10){
                    //大于10需要进位
                    flag = true;
                    curVal %= 10;
                }
                temp.next = new ListNode(curVal);
                temp = temp.next;
            }
        }
        if(flag){
            temp.next = new ListNode(1);
        }
        return l;
    }
}

代码冗长，重复

结合大佬的代码，做的改进之后：

    public static ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode pre = new ListNode(0);
        ListNode temp = pre;
        int carry = 0;
        while (l1 !=null || l2 != null || carry != 0) {
            int num1 = l1 == null ? 0 :l1.val;
            int num2 = l2 == null ? 0 :l2.val;
                //两个链表都还有数据,相加
                int curVal = num1 + num2 + carry;
                carry = curVal / 10;
                temp.next = new ListNode(curVal % 10);
                temp = temp.next;
                if(l1 != null) {
                    l1 = l1.next;
                }
                if(l2 != null) {
                    l2 = l2.next;
                }
        }

        return pre.next;
    }

1、原本的代码链表的第一位是在循环之外生成的，==>先创建一个pre预节点，给个默认数据0，只要最后返回的是pre.next即可

2、原本针对链表长度不一，分了三种情况==>大佬采用短链补0的方式，巧妙解决，值得注意的是如何让循环走下去，l1与l2何时需要后移。

3、原本是用一个布尔值标志是否要进位，进位就+1，加了之后恢复false==>用carry放进位的值? 无非是0或1

4、原本关于倒数第二位是否进位做了另外的判断==>放到了while条件里了