2. 两数相加

题目链接

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

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

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

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 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
• 题目数据保证列表表示的数字不含前导零

解法

刚看到这一题的时候感觉很简单，只需要将两个链表分别逆序拼接成两个数字然后再求和，再把最后的和逆序拆分成链表就可以了。结果发现这样根本不行，因为链表长度可能比较长，如果使用普通的int或者long型来接受中间计算的和的话，肯定是错误的。所以要避免出现总和的情况就只能逐位求和然后再使用尾插法组合成最终的链表。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p = l1;
    ListNode q = l2;
    ListNode head = new ListNode(0);
    ListNode curNode = head;
    //和大于等于10的时候要进一
    int carry = 0;
    while (p != null || q != null || carry == 1) {
        int m = (p == null) ? 0 : p.val;
        int n = (q == null) ? 0 : q.val;
        int tmp = m + n + carry;
        curNode.next = new ListNode(tmp % 10);
        curNode = curNode.next;
        carry = tmp / 10;
        if (p != null) {
            p = p.next;
        }
        if (q != null) {
            q = q.next;
        }
    }
    return head.next;
}