leetcode题目2：两数相加（java）

题目描述

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

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

解题思路

1. 由于链表是逆序存储，因此链表第一个节点就是最低位，需要从两个链表的头节点开始相加。
2. 对两个链表同时进行遍历，对两个链表的节点值相加，需要考虑上一次计算的进位问题。
3. 如果两个链表都遍历完了，仍存在进位，则需要在链表后添加一个节点。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    }
    if (l2 == null) {
        return l1;
    }

    int carry = 0;
    ListNode newHead = new ListNode(0);
    ListNode curNode = newHead;
    while (l1 != null || l2 != null || carry != 0) {
        int sum = 0;
        if (l1 == null && l2 == null) {
            sum = carry; // 链表遍历完了，但仍然存在进位
        } else if (l1 != null && l2 != null) {
            sum = l1.val + l2.val + carry;
        } else if (l1 != null) {
            sum = l1.val + carry;
        } else {
            sum = l2.val + carry;
        }

        carry = sum / 10; // 进位值
        curNode.next = new ListNode(sum % 10);
        curNode = curNode.next;

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