题目描述

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

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

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

示例：

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

https://leetcode-cn.com/problems/add-two-numbers/

思路1

首先链表是倒叙的，这就启发了我们可以用按位相加的方法逐步地求得结果。链表l1与l2相加，对应位相加后大于10，我们需要向前进位。下面的实现思路较为清晰，且易理解，但是有点笨拙。因为这涉及了三次的链表扫描。

1. 直接将l1与l2对应位相加
2. 扫描相加后的结果，如果大于等于10，向前进位
3. 重新扫描，将添加的多余节点剔除

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 342 + 465 = 807
        // 2—>4->3
        // 5->6->4
        // 7->10->7 => 7->0->8

        // 999 + 1 = 1000
        // 9->9->9
        // 1
        // 10->9->9 => 0->10->9 => 0->0->10 => 0->0->0->1

        ListNode head, next;
        next = head = new ListNode(0);
        // 第一次扫描，直接相加
        while(l1 !=null && l2 != null) {
            next.val = l1.val + l2.val;
            next.next = new ListNode(0);
            next = next.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        // 因为两个数长度不同，我们将剩余的部分写回到存放结果的链表
        while(l1 != null) {
            next.val = next.val + l1.val;
            next.next = new ListNode(0);
            next = next.next;
            l1 = l1.next;
        }

        while(l2 != null) {
            next.val = next.val + l2.val;
            next.next = new ListNode(0);
            next = next.next;
            l2 = l2.next;
        }
        // 第二次扫描，实现进位
        next = head;
        while(next.next != null){
            if(next.val >= 10){
                next.next.val += next.val / 10;
                next.val %= 10;
            }
            next = next.next;
        }

        if(next.val >= 10){
            next.next = new ListNode(next.val / 10);
            next.val %= 10;
        }
        // 第三次扫描，阶段因为new ListNode(0)产生的节点可能是多余的，例如[1] + [1] => [2，0]我们截断后的结果为[2]
        next = head;
        while(next.next != null) {
            if(next.next.next == null && next.next.val == 0) {
                next.next = null;
                break;
            }
            next = next.next;
        }
        return head;
    }
}

对于这种解法涉及到3次扫描，运行时间为29ms，“我的提交执行用时
已经战胜 93.99 % 的 java 提交记录”。我们还有优化的空间，争取一次扫描就能够完成计算。

思路2

我们能不能只用一个while循环就实现整个算法所需要的流程呢？我们使用while循环，条件为链表l1与l2任意之一遍历到尽头。在while内部有三种可能

1. l1与l2均未遍历到尽头
2. 只有l1未遍历到尽头
3. 只有l2未遍历到尽头

对于情况1，我们只需要将相应位置到数相加，保存的新建的链表节点中即可。需要注意的是，我们不能直接使用“=”覆盖新建链表节点到val字段，而是应该使用“+=”操作符。这样做是为了利用上，上次循环产生到进位符。对于情况2与3，我们用上次进位符与l1或l2到节点值相加即可。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head, next;
        next = head = new ListNode(0);

        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null) {
                next.val += l1.val + l2.val;
                l1 = l1.next;
                l2 = l2.next;
            } else if (l1 != null) {
                next.val += l1.val;
                l1 = l1.next;
            } else {
                next.val += l2.val;
                l2 = l2.next;
            }

            if (next.val >= 10) {
                next.val %= 10;
                next.next = new ListNode(1);
            } else if (l1 != null || l2 != null) {
                next.next = new ListNode(0);
            }
            next = next.next;
        }

        return head;
    }
}

为了处理相加后可能产生的进位情况，我们在后面判断新建节点的值是否大于等于10.若大于等于10，下一个新建的节点赋予初值1，否则赋初值0.