分析

• 本题的考点：模拟。

• 因为最低位在链表的头结点，因此处理比较容易，直接模拟一遍数学中的加法即可，将结果存入新的链表中。

• 为了处理方便，这里使用虚拟头结点的技巧。

代码

• C++

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        auto dummy = new ListNode(-1), cur = dummy;  // 虚拟头结点

        int t = 0;  // 记录进位
        while (l1 || l2 || t) {
            if (l1) t += l1->val, l1 = l1->next;
            if (l2) t += l2->val, l2 = l2->next;
            cur = (cur->next = new ListNode(t % 10));
            t /= 10;
        }
        return dummy->next;
    }
};

• Java

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(-1), cur = dummy;  // 虚拟头结点

        int t = 0;  // 记录进位
        while (l1 != null || l2 != null || t != 0) {
            if (l1 != null) {
                t += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                t += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(t % 10);
            cur = cur.next;
            t /= 10;
        }
        return dummy.next;
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为链表长度。

• 空间复杂度：$O(n)$，n为链表长度。