TechNomads

题目描述：

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

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

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

示例：

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

解法：

两个链表顺序遍历，对应两个节点的值相加作为新链表的值，如果产生进位，需要加到下一位。

• sumVal / 10 等于1就是产生了进位，为0则没有进位
• sumVal % 10则是新节点的值
• 构造root空节点，作为新链表的头节点（最终返回root.next节点）
• 构造游标节点的作用 ？ 为了标记处理新节点的当前位置
• 为什么不复用root节点新建了游标节点？这样做最终返回新节点时找不到头节点

Java代码如下：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int bit = 0;
        // 加了bit != 0 的条件是因为进位导致。如果两个链表最后一位相加产生进位，需要再建一个新节点
        while(l1 != null || l2 != null || bit != 0) {

            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            // 求和
            int sumVal = l1Val + l2Val + bit;
            bit = sumVal / 10;

            // 游标节点的下一个节点是新建的节点
            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;

            if (l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }

        return root.next;
    }

运行结果：