【算法100天 | 4】链表-两数相加（LeetCode 2）

LeetCode 2 两数相加

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

思路

首先我们输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加；特别注意10进制的两个 <10的整数相加，是存在进位的，所以每次计算链表相同位置的两个数（a、b）之和时需要考虑到前面的进位（carry）；即：链表处相应位置的数字为 (n1+n2+carry) % 10，而新的进位值为(n1+n2+carry) / 10。

另外，链表遍历结束后有可能carry>0，此时还需要在再增加一个链表节点，节点的值为carry（实际就是数字1）。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummyHead = new ListNode(0);
    ListNode cur = dummyHead;
    int carry = 0;
    while (l1 != null || l2 != null || carry > 0) {
        int value1 = l1 == null ? 0 : l1.val;
        int value2 = l2 == null ? 0 : l2.val;
        int sum = value1 + value2 + carry;
        carry = sum / 10;
        ListNode node = new ListNode(sum % 10);
        cur.next = node;
        cur = node;
        l1 = l1 == null ? null : l1.next;
        l2 = l2 == null ? null : l2.next;
    }
    return dummyHead.next;
}