画解算法：2. 两数相加

2019-07-15 本文已影响0人 DeppWang

题目链接

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

题目描述

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

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

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

示例：

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

解题方案

思路

使用进位变量carry存放进位值
使用一个假头节点dummyHead来链接“结果链表”，详见画解

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;//当前节点与dummyHead共同链接到curr.next
        int carry = 0;//用于进位，进位为1，默认为0
        while (l1 != null || l2 != null) {//使用||，因为l1和l2可能长度不一致
            int x = (l1 == null ? 0 : l1.val);//三元运算符避免l1.val报错
            int y = (l2 == null ? 0 : l2.val);
            int sum = x + y + carry;//carry为0时，对结果没有影响
            carry = sum / 10;//取整，0或1
            curr.next = new ListNode(sum % 10);//取余
            curr = curr.next;//当前节点变为下一个节点，循环的关键
            if (l1 != null)//不能为空，否则l1.next报错
                l1 = l1.next;//l1.next可以为空
            if (l2 != null)
                l2 = l2.next;//l2.next与l1.next均为空时，结束循环，避免无限循环
        }
        if (carry == 1) {//[5]+[5]->[10]
            curr.next = new ListNode(carry);
        }
        return dummyHead.next;//首节点不要
    }
}