2. 两数相加

分析

题目比较简单，就是两个数相加求和。按照加法思想，同时遍历两个链表，从个位一直加到最高位即可。比如要计算352+99，步骤如下：

1. 最低位 2+9得11，需进位，个位保留1，进位1先存储
2. 5+9 得 14，再加上刚刚的进位 1，得到 15，本位保留 5，进位 1 先存储
3. 3+0（注意此时 99 的位数已经用完了，但是 352 还有一位，所以这里可以将99的这一位看作0）得 3，再加上刚刚的进位 1，得到 4
4. 将前面几步中的数字按照顺序排列，可得到 451。

观察上述过程，一个容易出错的地方，在于加法进位的处理。另外一个难点，在于位数的处理，两个链表长度不一，结果链表的长度也只有把前面所有位数加完才确定。

一种实现

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const result = new ListNode(0, null);

    let p1 = l1;
    let p2 = l2;
    let cursor = result;

    while(p1 || p2 || cursor) {
        const result = cursor.val + (p1?.val ?? 0) + (p2?.val ?? 0);

        let tenDigit = result >= 10 ? 1 : 0;
        let singleDigit = result % 10;

        p1 = p1?.next ?? null;
        p2 = p2?.next ?? null;

        cursor.val = singleDigit;
        cursor.next = (p1 || p2 || tenDigit > 0) ? new ListNode(tenDigit, null) : null;
        cursor = cursor.next;
    }

    return result;
}