今日一题：LeetCode第二题：Add Two Numbers

题目：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 contains a single digit. Add the two numbers and return the sum as a linked list.

简言之：两个数相加，这两个数的数据结构以链表的形式给出，例如：754则为4->5->7，头结点是4，下面给两个例子：（其中l1、l2分别表示这两个数，即两个链表）

例子1：

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

例子2：

Input: l1 = [0], l2 = [0]
Output: [0]

分析一波：

两个数相加，按照我们小学数学学习的知识，列个竖式，从最低位（个位）开始，两两相加，逢十进一，如图：

好了，翻译成JAVA语言试下：

初版：

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 返回结果，也就是加和后的结果
        ListNode ret = null;
        // 这个是进位，为了让大家好理解，直接用了拼音
        int jinwei = 0;
        // l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0
        // 例如 76859 + 18 则可理解为：
        //   7 6 8 5 9
        // + 0 0 0 1 8
        while(l1 != null || l2 != null) {
            // 获取每一位的数值
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            // 每一位相加，同时加上进位
            int sum = n1 + n2 + jinwei;
            // 如果sum大于等于10，说明还得进位jinwei=1，同时当前数要减10；否则不进位，jinwei=0
            if (sum >= 10) {
                jinwei = 1;
                sum -= 10;
            } else {
                jinwei = 0;
            }
            // 好了，组装一下返回值
            ListNode current = new ListNode(sum);
            // 很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可
            if (ret == null) {
                ret = current;
            } else {
                ret.next = current;
              // 指针也往后移，准备下一位
                ret = ret.next;
            }
            // 当前位处理完了，指针往后移，准备处理下一位
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return ret;
    }
}

这个时候运行了一下，发现ret由于在31行一直后移，最后变成了尾结点，而我们要返回头结点，所以要修改下：

修改ret版：增加了3行~4行；31行；修改了44行

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 返回结果的头指针
        ListNode retHead = null; 
        // 返回结果，也就是加和后的结果
        ListNode ret = null;
        // 这个是进位，为了让大家好理解，直接用了拼音
        int jinwei = 0;
        // l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0
        // 例如 76859 + 18 则可理解为：
        //   7 6 8 5 9
        // + 0 0 0 1 8
        while(l1 != null || l2 != null) {
            // 获取每一位的数值
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            // 每一位相加，同时加上进位
            int sum = n1 + n2 + jinwei;
            // 如果sum大于等于10，说明还得进位jinwei=1，同时当前数要减10；否则不进位，jinwei=0
            if (sum >= 10) {
                jinwei = 1;
                sum -= 10;
            } else {
                jinwei = 0;
            }
            // 好了，组装一下返回值
            ListNode current = new ListNode(sum);
            // 很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可
            if (ret == null) {
                ret = current;
                retHead = current;
            } else {
                ret.next = current;
                ret = ret.next;
            }
            // 当前位处理完了，指针往后移，准备处理下一位
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        return retHead;
    }
}

运行后发现如下case有问题：

原来是最高位没有处理，比如99+9=108；目前算法会算成08，因为最后的进位没有处理，知道问题了就好解决了，如果最高位是进位，在处理下：

最终版：增加了44行~47行

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 返回结果的头指针
        ListNode retHead = null;
        // 返回结果，也就是加和后的结果
        ListNode ret = null;
        // 这个是进位，为了让大家好理解，直接用了拼音
        int jinwei = 0;
        // l1和l2只要有一个不为空就说明还可以继续加，为空的就直接加0
        // 例如 76859 + 18 则可理解为：
        //   7 6 8 5 9
        // + 0 0 0 1 8
        while(l1 != null || l2 != null) {
            // 获取每一位的数值
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            // 每一位相加，同时加上进位
            int sum = n1 + n2 + jinwei;
            // 如果sum大于等于10，说明还得进位jinwei=1，同时当前数要减10；否则不进位，jinwei=0
            if (sum >= 10) {
                jinwei = 1;
                sum -= 10;
            } else {
                jinwei = 0;
            }
            // 好了，组装一下返回值
            ListNode current = new ListNode(sum);
            // 很简单的逻辑，如果ret为空，说明是第一次相加（个位相加），current就是头结点；否则直接往后链即可
            if (ret == null) {
                ret = current;
                retHead = current;
            } else {
                ret.next = current;
                ret = ret.next;
            }
            // 当前位处理完了，指针往后移，准备处理下一位
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 最后有进位的话，最高位把1补上
        if (jinwei == 1) {
            ret.next = new ListNode(1);
        }
        return retHead;
    }
}

最终Accept，结果如下：

图片镇题：